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

Objec­tive: Given a binary tree and a given num­ber x, Write an recur­sive algo­rithm to search the ele­ment in the tree.

This is one of the very basic prob­lems of tree. If you are new to binary trees, this prob­lem might help you to under­stand the tree. First we will see the recur­sive solu­tion then I will show you how to solve it with­out recursion.

Approach:

Recur­sive Approach:

Approach will be very sim­ple, do any of the tree tra­ver­sal(inorder, pre­order, pos­torder, BFS or DFS) and check if given ele­ment is present.

Code:

Out­put:

```Does 4 exist in the tree: true

Does 7 exist in the tree: false
```

Non-Recursive Approach:

1. If we are not using recur­sion then we need a data struc­ture to store the tree tra­ver­sal, we will use queue here
2. Add root to the queue
3. Check if cur­rent node has the ele­ment we are look­ing for if yes then return true else add chil­dren nodes of cur­rent node to the queue
4. Ff queue gets empty, means we have not found the element

Code:

Out­put:

```Does 4 exist in the tree: true

Does 7 exist in the tree: false
```

#### You may also like...

• Ali Haider

very well explained…Search Ele­ment in Binary Search Tree is also explained with very easy demon­stra­tion here:
https://youtu.be/7v-6447o5Q8

• lipsa patel

Non Recur­sive approach can be done using stack.

pri­vate sta­tic boolean nonRecursiveSearchElementInBinaryTree(BinaryTreeNode root, int data) {
if (root != null) {

Stack stack1 = new Stack();

//Push root node
stack1.push(root);

while(!stack1.isEmpty()) {
Bina­ry­TreeN­ode poppedNode = stack1.pop();

if (poppedNode.data == data) {
return true;
}

if (poppedNode.left != null) {
stack1.push(poppedNode.left);
}

if(poppedNode.right != null) {
stack1.push(poppedNode.right);
}
}
}
return false;
}