Search in Binary Search Tree

Today, we will practice algorithm with a problem relating to binary search tree, which is, search in binary search tree.

Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example:

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

Analysis

This is a fairly easy problem. Intuitively, if value of current node is less than target value, we scan for left sub-tree, else value of current node is greater than target value, we scan for right sub-tree; do it until the value of current node equals to target value, then we return current node. If the end of tree is reached and no more node to scan, we return null.

We can solve this by using:

• either DFS to go as deep as possible until target value is found or no more possible node to scan.
• or, BFS with a queue to scan.

Solution

These two solutions are written in Java.

Using DFS

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) return root;

    return root.val > val ? searchBST(root.left, val) : searchBST(root.right, val);
}

Using BFS

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) return root;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        // if found
        if (node.val == val) return node;

        // if left node is available
        if (node.val > val && node.left != null) queue.offer(node.left);
        // if right node is available
        else if (node.val < val && node.right != null) queue.offer(node.right);
    }

    // target not found
    return null;
}

Additionally, in BFS approach, notice that we only offer into queue only one node each time, so we can simplify by using just a single extra variable to hold the current node.

public TreeNode searchBST(TreeNode root, int val) {
    if (root == null || root.val == val) return root;

    TreeNode node = root;

    while (node != null && node.val != val) {
        if (node.val < val) node = node.right;
        else if (node.val > val) node = node.left;
    }

    return node;
}

References

• LeetCode 700