Nov 15, 2013

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

           ,      No comments   
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 == 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;
  }
 }

}
=======Sample output=========
Searchng for key 12 : Found
Searchng for key 345 : Not found
Searchng for key 98 : Found
Searchng for key 981 : Not found
==========================
Location: Hyderabad, Telangana, India