700. Search in a Binary Search Tree

EasyView on LeetCode

Tree Binary Search Tree Binary Tree

Time: O(h)

Space: O(h)

Intuition

BST property: if val < node.val, go left; if val > node.val, go right; if equal, found.

Algorithm

1While node != null: if val==node.val return node. If val<node.val, node=node.left. Else node=node.right.
2Return null if not found.

Common Pitfalls

•Simple BST search — O(h) time. For balanced BST, O(log n).

700.cs

// Approach: Recursive BST search — go left if val < root, right if val > root;
// return the matching node or null.
// Time: O(h) Space: O(h)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

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

Was this solution helpful?