EASY NC#52 Blind #70 Trees

235. Lowest Common Ancestor of a Binary Search Tree

📖 Problem

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. According to the definition of LCA on Wikipedia: "The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself)."

🧠 Visual Learning Aid

1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases

JS/TS Refreshers

  • •Array methods (`push`, `pop`, `shift`, `slice`)
  • •Object/Map/Set usage patterns
  • •Function parameter and return typing
  • •Midpoint overflow-safe math
  • •Loop invariants
  • •Monotonic condition design

Logical Thinking Concepts

  • •Define invariants before coding
  • •Check edge cases first (`[]`, single element, duplicates)
  • •Estimate time/space before implementation
  • •Apply Binary Search reasoning pattern

💡 Approach

  • → BST property: left subtree < root < right subtree
  • → If both nodes are on same side, search that side
  • → If nodes are on different sides or one equals root, root is LCA
  • → Time: O(h), Space: O(h) where h is tree height

🛠️ Hints & Pitfalls

Hints

  • •BST property: left subtree < root < right subtree
  • •If both nodes are on same side, search that side
  • •If nodes are on different sides or one equals root, root is LCA

Common Pitfalls

  • •Time: O(h), Space: O(h) where h is tree height

🧪 Test Cases

Hidden tests on submit: 2

Test Case 1
Not run
Input:
_lowestCommonAncestor(_node1, _node2, _node3);
Expected:
{"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}
Test Case 2
Not run
Input:
_lowestCommonAncestor(_node1, _node2, _node2.right);
Expected:
{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}}
Test Case 3
Not run
Input:
_lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null);
Expected:
Computed from hidden reference

📝 Code Editor

📚 Reference Solution

▼

🔗 Related Problems

#98 Validate Binary Search Tree #100 Same Tree #104 Maximum Depth of Binary Tree #105 Construct Binary Tree from Preorder and Inorder Traversal #110 Balanced Binary Tree
⌘K Search ⌘↩ Run ⌘S Submit