Topics covered
1. Search an element in binary tree - Recursive2. Search an element in binary tree - Iterative
3. Complete sample program- 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;
}
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;
}
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 == true ? "Found" : "Not found")); nodesStr = serObj.searchAnElementInBinaryTreeRecursive(root, 345); System.out.println("Searchng for key 345 : " + (nodesStr == true ? "Found" : "Not found")); nodesStr = serObj.searchAnElementInBinaryTreeRecursive(root, 98); System.out.println("Searchng for key 98 : " + (nodesStr == true ? "Found" : "Not found")); nodesStr = serObj.searchAnElementInBinaryTreeRecursive(root, 981); System.out.println("Searchng for key 981 : " + (nodesStr == true ? "Found" : "Not found")); } 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; } } }
Searchng for key 12 : Found
Searchng for key 345 : Not found
Searchng for key 98 : Found
Searchng for key 981 : Not found
==========================