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.

by nikoo28
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
sample_treeOutput: 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)

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

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More