Solving Lowest Common Ancestor of a Binary Search Tree: Finding a Common Node

The "Lowest Common Ancestor of a Binary Search Tree" problem focuses on finding the lowest (or deepest) common ancestor of two nodes in a BST. The lowest common ancestor is defined as the lowest node in the tree that has both nodes as descendants.

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

Example

Consider a binary search tree:

The lowest common ancestor of nodes 2 and 8 is 6.

Solution Approach - Iterative Traversal

Breaking Down the Solution

• Iterative Search: Iteratively traverse the tree starting from the root.
• Decision Making: If both nodes p and q are smaller than the current node, move to the left subtree. If both are larger, move to the right subtree.
• Finding LCA: The first node where p and q split into different directions is the LCA.

Conclusion

Finding the Lowest Common Ancestor in a BST is a fundamental problem in tree algorithms, demonstrating the efficiency of BST properties in solving search-related queries.

Rust Solution

Rust's ? operator collapses the whole null-walk into the traversal: let mut node = root? bails out with None when the tree is empty, and node.left.as_ref()? / node.right.as_ref()? return early the instant a child is absent, replacing the TS while truthiness check. .as_ref() is required because each Option<Box<TreeNode>> child is owned by a node the function only borrows — it turns &Option<Box<TreeNode>> into Option<&Box<TreeNode>> so the walk lends out a reference instead of moving the box out of the tree. The explicit lifetime 'a on Option<&'a TreeNode> ties the returned reference back to the borrowed root, which is what lets the caller unwrap() and read .val with no ownership transfer at all.

Go Solution

Go leans on typed nil pointers throughout: node := root walks *TreeNode links, for node != nil is the loop guard, and return nil hands back a typed nil pointer when p and q never split into different subtrees. The newTreeNode constructor returns &TreeNode{val: val}, a composite literal that sets only val and leaves left/right at their zero value (nil), so leaf nodes need no explicit child assignment. Where the TS version returns null, the Go equivalent returns nil outright rather than any empty-node placeholder.