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 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