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

Write a program to search an element in a binary tree.

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

One simple way of solving this problem is to find the element in the left sub-tree, in the right sub-tree, and in the root data. This approach can be easily implemented with recursion.

This approach works because each node of the tree has 3 parts -> the root, the left and the right.
What we do is we see if the element is present in these 3 parts.

  • Left Sub-tree -> Left = 7 (Not matching), Right = 9 (Not Matching), Root = 2 (Not Matching)
  • Right Sub-tree -> Left = 5 (Not matching), Right = 4 (Not Matching), Root = 3 (Match)
  • Root -> 1 (Not Matching)

Since a match was found, we return true.

Here is an implementation using recursion.

#include<stdio.h>
#include<malloc.h>

struct binaryTreeNode{
	int data;
	struct binaryTreeNode * left;
	struct binaryTreeNode * right;
};

// A recursive function to find the element in tree
// Parameters - root of the tree and element to search
int findElementInTreeRecursive(struct binaryTreeNode * root, int num)
{
	// A variable for root value
	int root_val;

	// Variable to store values in left and right tree
	int left, right;

	if(root != NULL)
	{
		// Get the root value
		root_val = root -> data;

		if(root_val == num)
			return 1;

		// Find the element in left sub-tree
		// If found, we return 1
		left = findElementInTreeRecursive(root -> left, num);
		if(left == 1)
			return 1;
		else
		{
			// We need to find the element in right sub-tree
			right = findElementInTreeRecursive(root -> right, num);
			if(right == 1)
				return 1;
		}
	}

	// If we reach here, that means the element was not found
	return 0;
}

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

Ideone link for running program:- http://ideone.com/TSCKOM

Method 2Find an element in a binary tree without using recursion.

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