Home Trees Write a program to search an element in a binary tree without using recursion.

# Write a program to search an element in a binary tree without using recursion.

0 comment

Question: Given the root pointer to a binary tree, find if an element is present in it.

Input: Sample Tree (Pointer to node 1 is given), Search – 3 Output: Present

We discussed how to find if an element exists in the binary tree in this post.

That involved recursion. If recursion seems difficult to you, we can even solve this problem with the help of level order traversal of binary tree. The property of level order traversal is that it passes through each element of the binary tree. Utilizing this property we can keep a track of all the elements that are present in the tree. We can compare each element with our number and return true if its present. Here is an implementation to find the element without using recursion.

int findElementInTreeNonRecursive(struct binaryTreeNode * root, int num)
{
int found = 0;

// Level Order Traversal
struct binaryTreeNode * temp = NULL;
struct queue * Q = NULL;
if(root == NULL)
return;

Q = enQueue(Q, root);

while(!isQueueEmpty(Q))
{
temp = Q -> front -> data;

Q = deQueue(Q);

// Find the element
if(temp -> data == num)
{
found = 1;
break;
}

if(temp -> left)
Q = enQueue(Q, temp -> left);
if(temp -> right)
Q = enQueue(Q, temp -> right);
}
free(Q);

// Return 1 if element was found
return found;
}


Time Complexity:- O(n)
Space Complexity:- O(n)