Given a Binary tree and a node. The task is to search and check if the given node exists in the binary tree or not. If it exists, return True otherwise return False.
Examples:
Input: Node = 4 Output: true Input: Node = 40 Output: false
Solution:
Approach 1: Recursive
boolean searchNode(TreeNode root, TreeNode node){
if(root == null)
return false;
// visit node
if (root.val == node.val)
return true;
// Search in left subtree
if(searchNode(root.left, node)){
return true;
}
// Search in right subtree
if(searchNode(root.right, node)){
return true;
}
// If not found in left and right subtree
return false;
}
Complexity:
- Time: O(n)
- Space: O(n) Recursion stack space
Approach 2: Iterative
boolean searchTreeNode(TreeNode root, TreeNode node){
Deque<TreeNode> stack = new ArrayDeque<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode curr = stack.pop();
if(curr.val == node.val){
return true;
}
// push right node first
if(curr.right != null){
stack.push(curr.right);
}
// then push left node
if(curr.left != null){
stack.push(curr.left);
}
}
return false;
}
Complexity:
- Time: O(n)
- Space: O(n) Stack space