LeetCode 700: Search in a Binary Search Tree

Meta Data

#

Difficulty: easy First Attempt: 2022-08-31

• Submissions: Accepted (first try)

Approach

#

BST search (Tree Template 3): larger than the target goes left, smaller goes right, equal is found; reaching None means absent.

My Solution

#

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        while root and root.val != val:
            root = root.left if val < root.val else root.right
        return root

Complexity

#

Time O(h), space O(1).

Mistakes to Avoid

#

• Return the node (its whole subtree), not the value.

Interview Explanation

#

From the root I go left when larger and right when smaller, returning on a match or at None. Time O(h), space O(1).