# Search(find) an element in binary tree in Java - Recursive and Iterative

In order to search a key element in binary tree we can use any traversal algorithm like recursive pre-order and iterative pre-order traversal. Instead of processing/displaying it we need check whether key value is equal to node data.

Sample code for searching  an element in binary tree in Java - recursive approach

```/* Recursive pre-order to search for an element in binary tree */
public boolean searchAnElementInBinaryTreeRecursive(Node root, int key) {
// boolean isFound = false;
if (root == null) {
return false;
}
if (root.data == key) {
return true;
}
if (searchAnElementInBinaryTreeRecursive(root.leftChild, key)) {
return true;
} else if (searchAnElementInBinaryTreeRecursive(root.rightChild, key)) {
return true;
}
return false;
}```
Explanation:- key in method parameter is the value that we are looking in binary tree.In recursive pre-order traversal, at any moment, if root data is same as key value then return true to calling method. First, traverse left sub-tree followed by right sub-tree. If key is not same as node data, function return false.

Sample code for searching  an element in binary tree in Java - iterative approach

```/* Using iterative pre-order to search for an element in binary tree */
public boolean searchAnElementInBTIterative(Node root, int key) {
boolean isFound = false;
/* java.util.Stack */
Stack<Node> stack = new Stack<>();
if (root != null) {
/* push root into stack if root is not null */
stack.push(root);
/* Loop until stack is not empty */
while (!stack.isEmpty()) {
root = stack.pop();
/* Do check for key == node value, if true break loop */
if (root.data == key) {
isFound = true;
break;
}
Node lc = root.getLeftChild();
Node rc = root.getRightChild();

/* If right child exist, push into stack */
if (rc != null) {
stack.push(rc);
}
/* If left child exist, push into stack */
if (lc != null) {
stack.push(lc);
}
}// End while loop
}
return isFound;
}```
Explanation:- In iterative pre-order traversal, after popping an element from stack - instead of processing or displaying check whether key is same as node data(root.data), if true mark isFound= true and break loop and return isFound. Once stack is empty(key not found) and loop terminates, returns isFound.

Complete sample program: search an element in binary tree in Java- recursive and iterative
```package com.devinline.trees;

import java.util.Stack;

public class SearchAnElementInBT {
/* Recursive pre-order to search for an element in binary tree */
public boolean searchAnElementInBinaryTreeRecursive(Node root, int key) {
// boolean isFound = false;
if (root == null) {
return false;
}
if (root.data == key) {
return true;
}
if (searchAnElementInBinaryTreeRecursive(root.leftChild, key)) {
return true;
} else if (searchAnElementInBinaryTreeRecursive(root.rightChild, key)) {
return true;
}
return false;
}

/* Using iterative pre-order to search for an element in binary tree */
public boolean searchAnElementInBTIterative(Node root, int key) {
boolean isFound = false;
/* java.util.Stack */
Stack<Node> stack = new Stack<>();
if (root != null) {
/* push root into stack if root is not null */
stack.push(root);
/* Loop until stack is not empty */
while (!stack.isEmpty()) {
root = stack.pop();
/* Do check for key == node value, if true break loop */
if (root.data == key) {
isFound = true;
break;
}
Node lc = root.getLeftChild();
Node rc = root.getRightChild();

/* If right child exist, push into stack */
if (rc != null) {
stack.push(rc);
}
/* If left child exist, push into stack */
if (lc != null) {
stack.push(lc);
}
}// End while loop
}
return isFound;
}

public static void main(String[] args) {
SearchAnElementInBT serObj = new SearchAnElementInBT();
Node root = serObj.new BinaryTree().createTree();
boolean nodesStr = serObj
.searchAnElementInBinaryTreeRecursive(root, 12);
System.out.println("Searchng for key 12 : "
nodesStr = serObj.searchAnElementInBinaryTreeRecursive(root, 345);
System.out.println("Searchng for key 345 : "

nodesStr = serObj.searchAnElementInBinaryTreeRecursive(root, 98);
System.out.println("Searchng for key 98 : "

nodesStr = serObj.searchAnElementInBinaryTreeRecursive(root, 981);
System.out.println("Searchng for key 981 : "

}

class BinaryTree {
Node root;

public BinaryTree() {
root = null;
}

public Node createTree() {
if (root == null) {
root = new Node(12);
}
root.setLeftChild(new Node(23));
root.setRightChild(new Node(18));
root.getLeftChild().setLeftChild(new Node(11));
root.getLeftChild().setRightChild(new Node(43));
root.getRightChild().setLeftChild(new Node(12));
root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
root.getLeftChild().getLeftChild().setRightChild(new Node(78));
root.getRightChild().getLeftChild().setRightChild(new Node(98));
return root;
}
}

class Node {

private int data;
private Node leftChild;
private Node rightChild;

public Node(int data) {
this.data = data;
leftChild = null;
rightChild = null;
}

public int getData() {
return data;
}

public void setData(int data) {
this.data = data;
}

public Node getLeftChild() {
return leftChild;
}

public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}

public Node getRightChild() {
return rightChild;
}

public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
}

}```
=======Sample output=========
Searchng for key 12 : Found