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

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.

• Find if an element is present in a binary tree

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)

Ideone link:- http://ideone.com/tzK8CJ