Search in a Binary Search Tree

LeetCode 783 | Difficulty: Easy

Easy

Problem Description

You are given the root of a binary search tree (BST) and an integer val.

Find the node in the BST that the node's value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

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 <= 10^7`

- `root` is a binary search tree.

- `1 <= val <= 10^7`

Topics: Tree, Binary Search Tree, Binary Tree

---

Approach

Direct Approach

This problem can typically be solved with straightforward iteration or simple data structure usage. Focus on correctness first, then optimize.

When to use

Basic problems that test fundamental programming skills.

---

Solutions

Solution 1: C# (Best: 120 ms)

Metric	Value
Runtime	120 ms
Memory	34 MB
Date	2020-02-21

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode SearchBST(TreeNode root, int val) {
        if(root==null) return null;
        if(root.val == val) return root;
        else if(root.val < val) return SearchBST(root.right, val);
        else return SearchBST(root.left, val);
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Consider: "What information do I need from each subtree?" — this defines your recursive return value.