Search in a Binary Search Tree

Problem Statement

In this problem, you are given a binary search tree (BST) which is represented by its root node, and a specific integer value (val). Your task is to find the node within the BST whose value is exactly equal to val. Once the node is found, you are required to return the entire subtree that originates from this node. If no such node with the value val exists in the BST, your function should return null. This requires an effective traversal of the BST, leveraging its properties to efficiently locate the desired node.

Examples

Example 1

Input:

root = [4,2,7,1,3], val = 2

Output:

[2,1,3]

Example 2

Input:

root = [4,2,7,1,3], val = 5

Output:

[]

Constraints

• The number of nodes in the tree is in the range [1, 5000].
• 1 <= Node.val <= 107
• root is a binary search tree.
• 1 <= val <= 107

Approach and Intuition

To solve this problem, understanding the properties of a binary search tree is crucial. A BST is a binary tree where the value of each node must be greater than all the values stored in its left subtree and less than those in its right subtree.

1. Start from the root and compare the val with the value of the current node.
   • If the value matches, then the current node is the node we're looking for. Return this node and all its descendants as the subtree.
   • If val is less than the current node's value, move to the left child of the node.
   • If val is greater than the current node's value, move to the right child of the node.
2. If you reach a leaf node (i.e., null) without finding the value, it means the node doesn't exist in the tree. Return null in this case.

Key Pointers:

• Traversal: Since the BST is ordered, a linear search is not necessary; instead, a directional search based on value comparisons can significantly reduce the search space.
• Efficiency: The maximum number of comparisons in the worst case will be equal to the height of the BST, which can be optimized if the BST is balanced.
• Edge Cases: Consider the scenario where the tree is empty (root is null), or all nodes have the same value, which isn't equal to val. Always ensure to check if a node is null before attempting to access its value or children.

By following this structured approach, the appropriate subtree can be identified and returned efficiently, adhering to the constraints and properties of BSTs.

Solutions

class Solution {
  public TreeNode findInBST(TreeNode node, int target) {
    while (node != null && target != node.val)
      node = target < node.val ? node.left : node.right;
    return node;
  }
}