*916*

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.