DKodeTree Small Logo
DKodeTreeWhere logic takes root...!
Search in a Binary Search Tree - Solution
Solutions and explanations
Link to Problem StatementView on GitHubWatch Video

Video Explanation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        if not root:
            return None
        if val < root.val:
            return self.searchBST(root.left, val)
        elif val > root.val:
            return self.searchBST(root.right, val)
        return root

Complexity Analysis

Here, h is the height of the Binary Search Tree.

  • Time Complexity: O(h)
    • At each recursive call, we move to either the left or right child based on the target value, so the number of recursive steps is bounded by the height of the tree.
  • Space Complexity: O(h)
    • Due to space used by recursion stack.

Note: In worst case height can go upto n (where n is the number of nodes).

  • Best case: In a balanced BST: h = log(n)
  • Worst Case: In a skewed BST (e.g., all left-children or right-children): h = n

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        cur = root
        while cur:
            if cur.val > val:
                cur = cur.left
            elif cur.val < val:
                cur = cur.right
            else:
                return cur
        return None

Complexity Analysis

Here, h is the height, and n is the number of nodes in the Binary Search Tree.

  • Time Complexity: O(h)

    • At each step, we move to either the left or right child based on the target value, so the number of recursive steps is bounded by the height of the tree.
      • Best case: In a balanced BST: h = log(n)
      • Worst Case: In a skewed BST (e.g., all left-children or right-children): h = n

  • Space Complexity: O(1)

    • Constant space — just one variable for traversal.