Look Up a Key and Return Its Whole Subtree

Easy10–15 min

Topics

Binary Search TreeBSTSearchIteration

Companies

AmazonMicrosoftAdobeOracle

You are given the root of a binary search tree (every node's left subtree holds smaller values and its right subtree holds larger values, and all values are distinct) and an integer key. Find the node that holds key and return it — that is, return the whole subtree that starts at that node. If no node holds key, return an empty tree.

You can search every node like in any binary tree, but the ordering lets you discard one whole side at each step.

Test Case 1:

Input:root = [40, 20, 60, 10, 30, 50, 70, null, null, 25, 35], key = 30

Output:[30, 25, 35]

Explanation:Node 30 is found under 20; its subtree is 30 with children 25 and 35.

Test Case 2:

Input:root = [40, 20, 60, 10, 30, 50, 70, null, null, 25, 35], key = 45

Output:[]

Explanation:45 would have to sit below 50 (left side), but 50 has no left child — the key is not present.

Test Case 3:

Input:root = [40, 20, 60, 10, 30, 50, 70, null, null, 25, 35], key = 60

Output:[60, 50, 70]

Explanation:The node 60 and both of its children.

Constraints

◆0 ≤ number of nodes ≤ 100; all node values are distinct, 0 ≤ node.val ≤ 1000
◆The tree is a binary search tree: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. It is given as its root node (null for an empty tree)
◆key is any integer between 0 and 1000 (it may or may not be in the tree)
◆Return the node holding key, i.e. the whole subtree that starts there (it is checked as a level-order list). If key is not in the tree, return an empty tree

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Search Every Node as if It Were an Ordinary Tree

Brute

Ignore the ordering rule and treat the tree like any binary tree: check the current node, then search the left subtree, and if nothing was found there, search the right subtree. It always works, but on a miss (or a key on the right) it may visit every node: O(n) time, O(h) recursion space. It throws away everything the search-tree property tells us.

TimeO(n)

SpaceO(h)

Java

Try it out

class Solution {
    public TreeNode findSubtree(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) return root;
        TreeNode left = findSubtree(root.left, key);
        if (left != null) return left;
        return findSubtree(root.right, key);
    }
}

Optimal — Follow the Ordering: Go Left or Right, Never Both

Optimal

In a binary search tree, if the key is smaller than the current node's value it can only be in the left subtree, and if it is larger it can only be in the right subtree — so half of the possibilities are discarded at every step. Walk down from the root with a loop: stop when the current node is empty (key absent) or holds the key (found), otherwise step left or right. The work is the height of the tree: O(h) time (O(log n) for a balanced tree) and O(1) space.

TimeO(h)

SpaceO(1)