Search an element in binary tree without recursion.

We can use level order traversal for solving this problem. The only change required in level order traversal is, instead of printing the date we just need to check whether the root data is equal to the element we want to search.

source: Data Structures and Algorithms Made Easy in Java ( By Narasimha Karumanchi )

Java implementation is as below:

package askgif.tree;

import java.util.LinkedList;
import java.util.Queue;

class Node
{
 int data;
 Node left, right;
 
 public Node(int item)
 {
 data = item;
 left = right = null;
 }
}

class BinaryTree
{
 Node root;
 
 BinaryTree()
 {
 root = null;
 }
 
}

public class TreeQuestions {

	public static void main(String[] args) {
		BinaryTree binaryTree = new BinaryTree();
		Node root = new Node(1);
		binaryTree.root = root;
		binaryTree.root.left = new Node(2);
		binaryTree.root.right = new Node(3);
		
		binaryTree.root.left.left = new Node(4);
		binaryTree.root.left.right = new Node(5);
 
		int data = 4;
 System.out.println(SearchUsingLevelOrder(root, data));

	}

	private static Boolean SearchUsingLevelOrder(Node treeNode, int data) {
		if(treeNode == null)
			return false;
		
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(treeNode);
		
		while(!queue.isEmpty()) {
			Node temp = queue.remove();
			if(temp.data == data)
				return true;
			if(temp.left != null)
				queue.add(temp.left);
			if(temp.right != null)
				queue.add(temp.right);
		}
		
		return false;
	}

}

output:

true

Time Complexity: O(n) for traversing each node

Space Complexity: O(n) for storing elements in a queue.