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

References: