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

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

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 2 – Find an element in a binary tree without using recursion.