Problem

Given a binary tree and a target number x, write a recursive algorithm to determine if the number exists within the binary tree. If the target number exists in the tree, return True; otherwise, return False.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input: 
Binary Tree:
        8
       / \
      3   10
     / \    \
    1   6    14
Target Number: 6
 
Output:  True
 
Explanation:
The number `6` exists in the binary tree as a left child of node `3`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

Input: 
Binary Tree:
        8
       / \
      3   10
     / \    \
    1   6    14
Target Number: 7
 
Output: False
 
Explanation:
The number `7` does not exist in the binary tree.

Solution

Method 1 - DFS

The problem can be approached using Depth First Search (DFS). When searching for x in a binary tree, we recursively explore the left and right subtrees until:

  1. We find the target x and return True.
  2. We reach a leaf node (null/None) and return False.

Approach

  1. Start from the root node.
  2. If the root node is null, return False.
  3. If the root node’s value is equal to x, return True.
  4. Recursively search for x in the left subtree and the right subtree.
  5. Combine the results of the subtrees using an OR operation to determine if x exists in either subtree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Solution {
    public boolean isPresent(TreeNode root, int x) {
        // Base case: if the node is null, return false
        if (root == null) {
            return false;
        }

        // If the current node matches the value, return true
        if (root.val == x) {
            return true;
        }

        // Recursively check left and right subtrees
        boolean leftSearch = isPresent(root.left, x);
        boolean rightSearch = isPresent(root.right, x);

        // Combine the results of left and right subtrees
        return leftSearch || rightSearch;
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);

        Solution sol = new Solution();
        System.out.println(sol.isPresent(root, 6)); // Output: true
        System.out.println(sol.isPresent(root, 7)); // Output: false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution:
    def isPresent(self, root, x):
        # Base case: if the node is None, return False
        if not root:
            return False

        # If the current node matches the value, return True
        if root.val == x:
            return True

        # Recursively check left and right subtrees
        left_search = self.isPresent(root.left, x)
        right_search = self.isPresent(root.right, x)

        # Combine the results of left and right subtrees
        return left_search or right_search


# Example usage
if __name__ == "__main__":
    # Construct binary tree
    root = Solution.TreeNode(8)
    root.left = Solution.TreeNode(3)
    root.right = Solution.TreeNode(10)
    root.left.left = Solution.TreeNode(1)
    root.left.right = Solution.TreeNode(6)
    root.right.right = Solution.TreeNode(14)

    sol = Solution()
    print(sol.isPresent(root, 6))  # Output: True
    print(sol.isPresent(root, 7))  # Output: False

Complexity

  • ⏰ Time complexity: O(n), as each node in the binary tree is visited once during the recursive traversal.
  • 🧺 Space complexity: O(h) as the recursion depth corresponds to the height of the tree, where H is the height of the binary tree.

Method 2 - Level order traversal

To implement this method, we perform a Breadth-First Search (BFS) by traversing the binary tree level by level using a queue. At each step, we:

  1. Dequeue the front node and check whether it matches the target value x.
  2. If the value is found, return True.
  3. Otherwise, enqueue the left and right children of the current node (if they exist).
  4. If the queue becomes empty and the value is not found, return False.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

class Solution {
    public boolean isPresent(TreeNode root, int x) {
        // Base case: if the root is null, the value cannot be present
        if (root == null) {
            return false;
        }

        // Create a queue for BFS
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root); // Add root to the queue

        while (!queue.isEmpty()) {
            // Retrieve and remove the front node from the queue
            TreeNode current = queue.poll();

            // Check if the current node's value matches the target
            if (current.val == x) {
                return true;
            }

            // Add the left child to the queue if it exists
            if (current.left != null) {
                queue.offer(current.left);
            }

            // Add the right child to the queue if it exists
            if (current.right != null) {
                queue.offer(current.right);
            }
        }

        // If we exhaust the tree without finding x, return false
        return false;
    }

    // Example usage
    public static void main(String[] args) {
        TreeNode root = new TreeNode(8);
        root.left = new TreeNode(3);
        root.right = new TreeNode(10);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(6);
        root.right.right = new TreeNode(14);

        Solution sol = new Solution();
        System.out.println(sol.isPresent(root, 6)); // Output: true
        System.out.println(sol.isPresent(root, 7)); // Output: false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution:

    def isPresent(self, root, x):
        # Base case: if the root is None, return False
        if not root:
            return False

        # Create a queue for BFS
        queue = deque([root])  # Initialize the queue with the root node

        while queue:
            # Retrieve and remove the front node from the queue
            current = queue.popleft()

            # Check if the current node's value matches the target
            if current.val == x:
                return True

            # Add the left child to the queue if it exists
            if current.left:
                queue.append(current.left)

            # Add the right child to the queue if it exists
            if current.right:
                queue.append(current.right)

        # If we exhaust the tree without finding x, return False
        return False


# Example usage
if __name__ == "__main__":
    # Construct binary tree
    root = Solution.TreeNode(8)
    root.left = Solution.TreeNode(3)
    root.right = Solution.TreeNode(10)
    root.left.left = Solution.TreeNode(1)
    root.left.right = Solution.TreeNode(6)
    root.right.right = Solution.TreeNode(14)

    sol = Solution()
    print(sol.isPresent(root, 6))  # Output: True
    print(sol.isPresent(root, 7))  # Output: False

Complexity

  • ⏰ Time complexity: O(n), as each node in the binary tree is visited once during the recursive traversal.
  • 🧺 Space complexity: O(w) as maximum space required for the queue is proportional to the maximum number of nodes at any single level of the binary tree, where W is the tree’s width.