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

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

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

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

#### You may also like

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