Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import java.util.LinkedList;
import java.util.Queue;
public class T_SearchElementInTreeWithOutRecursion {
// If we are not using recursion then we need a data structure to store the
// tree traversal, we will use queue here
public static boolean isPresent(Node root, int x) {
if (root != null) {
Queue<Node> q = new LinkedList<>();
// add root to the queue
q.add(root);
while (!q.isEmpty()) {
Node n = q.poll();
// check if current node has the element we are looking for
if (n.data == x) {
return true;
}
// add children to the queue
if (n.left != null) {
q.add(n.left);
}
if (n.right != null) {
q.add(n.right);
}
}
// if reached here, means we have not found the element
return false;
}
// if root is null, return false
return false;
}
public static void main(String[] args) {
Node root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
System.out.println("Does 4 exist in the tree: " + isPresent(root, 4));
System.out.println("Does 7 exist in the tree: " + isPresent(root, 7));
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment