# Search the Element in a binary tree – With and Without Recursion

Objective: Given a binary tree and a given number x, Write an recursive algorithm to search the element in the tree.

This is one of the very basic problems of tree. If you are new to binary trees, this problem might help you to understand the tree. First we will see the recursive solution then I will show you how to solve it without recursion.

Approach:

Recursive Approach:

Approach will be very simple, do any of the tree traversal(inorder, preorder, postorder, BFS or DFS) and check if given element is present.

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 //Approach will be very simple, do any of the tree traversal and check if given element is present. public class T_SearchElementInTree { public static boolean isPresent(Node root, int x) { if (root != null) { // check if current node has the element we are looking for if (root.data == x) { return true; } else { // check if the sub trees return isPresent(root.left, x) || isPresent(root.right, x); } } return false; } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println("Does 4 exist in the tree: " + isPresent(root, 4)); System.out.println("Does 7 exist in the tree: " + isPresent(root, 7)); } } class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } }

Output:

```Does 4 exist in the tree: true

Does 7 exist in the tree: false
```

Non-Recursive Approach:

1. If we are not using recursion then we need a data structure to store the tree traversal, we will use queue here
2. Add root to the queue
3. Check if current node has the element we are looking for if yes then return true else add children nodes of current node to the queue
4. Ff queue gets empty, means we have not found the element

Code:

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

 import java.util.LinkedList; import java.util.Queue; public class T_SearchElementInTreeWithOutRecursion { // If we are not using recursion then we need a data structure to store the // tree traversal, we will use queue here public static boolean isPresent(Node root, int x) { if (root != null) { Queue q = new LinkedList<>(); // add root to the queue q.add(root); while (!q.isEmpty()) { Node n = q.poll(); // check if current node has the element we are looking for if (n.data == x) { return true; } // add children to the queue if (n.left != null) { q.add(n.left); } if (n.right != null) { q.add(n.right); } } // if reached here, means we have not found the element return false; } // if root is null, return false return false; } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.left.right = new Node(5); System.out.println("Does 4 exist in the tree: " + isPresent(root, 4)); System.out.println("Does 7 exist in the tree: " + isPresent(root, 7)); } } class Node { int data; Node left; Node right; public Node(int data) { this.data = data; } }

Output:

```Does 4 exist in the tree: true

Does 7 exist in the tree: false
```