Start learning free

LESSON 344 OF 442 · BINARY TREES

Lowest Common Ancestor in a BST in Go: O(h) Iterative Walk

Practice O(n) Read the full explanation

Given the root of a binary search tree (BST) and two values p and q that are both in the tree, return the value of their lowest common ancestor.

The lowest common ancestor of p and q is the deepest node that has both of them in its subtree. A node counts as its own ancestor: if the node holding p is above the node holding q, the answer is p.

In a BST, every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.

The trees below are written in level order (top to bottom, left to right), with nil for a missing child.

 

Example 1:

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

Input: root = [6,2,8,0,4,7,9,nil,nil,3,5], p = 2, q = 8
Output: 6
Explanation: 2 is in the left subtree of 6 and 8 is in its right subtree, so 6 is the deepest node that has both below it.

Example 2:

Input: root = [6,2,8,0,4,7,9,nil,nil,3,5], p = 2, q = 4
Output: 2
Explanation: 4 is in the subtree of 2, and a node counts as its own ancestor.

Example 3:

Input: root = [6,2,8,0,4,7,9,nil,nil,3,5], p = 5, q = 3
Output: 4
Explanation: 3 and 5 are the two children of 4, one on each side.

 

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • Each node value is between -104 and 104, and all values are different.
  • p and q are both values of nodes in the tree. They can be equal.

 

Follow up: Can you find it in O(h) time, where h is the height of the tree, using only O(1) extra space?
STEP 1 OF 6
    Ctrl + Enter to check

    GO · BINARY TREES

    Lca In Bst in Go, explained

    Problem overview

    The function lowestCommonAncestor receives the root of a binary search tree (BST) and two values, p and q, that are both in the tree. It returns the value of their lowest common ancestor: the deepest node that has both of them in its subtree. A node counts as its own ancestor, and p and q may be equal. The tree has 1 to 1,000 nodes with distinct values.

    In the tree with root 6, children 2 and 8, then 0, 4, 7, 9 below, and 3 and 5 below 4:

    • for 2 and 8 the answer is 6, because they are in different subtrees of 6;
    • for 2 and 4 the answer is 2, because 4 is in the subtree of 2 and 2 counts as its own ancestor;
    • for 5 and 3 the answer is 4, which has them as its two children.

    Approach: let the values choose the direction

    In a plain binary tree you would have to search both subtrees. A BST gives more information: everything smaller than a node's value is in its left subtree, and everything larger is in its right subtree. So at any node you can tell where p and q are without looking.

    Start at the root, which is above every node and so is always a common ancestor. Then ask where the two values are relative to the current node:

    • both smaller: both lie in the left subtree, so the lowest common ancestor is there too, and you can move left;
    • both larger: move right;
    • otherwise, they are on different sides, or one of them is the current node's value. Going down either way would lose one of them, so the current node is the answer.

    Each pass goes down one level, so the walk takes at most as many passes as the tree is tall. That is the O(h) time of the follow-up, with no recursion and no stack, so O(1) extra space.

    Step by step

    1. Declare node and set it to root. It marks the node the walk is at.
    2. Loop while node != nil. In Go, a for with only a condition is the while loop. Each pass looks at one node and either returns or moves one level down.
    3. If p and q are both smaller than node.Val, joined with &&, set node to node.Left.
    4. Else if both are larger, set node to node.Right.
    5. Otherwise return node.Val. The values split here, or one of them equals the node's value, and in both cases this node is the deepest one with both below it.
    6. Return -1 after the loop. Because both values are in the tree, the loop always returns first, but Go requires a function that returns an int to end with a return.

    The solution in Go

    func lowestCommonAncestor(root *TreeNode, p, q int) int {
	node := root
	for node != nil {
		if p < node.Val && q < node.Val {
			node = node.Left
		} else if p > node.Val && q > node.Val {
			node = node.Right
		} else {
			return node.Val
		}
	}
	return -1
}

    Go details worth a closer look:

    • Pointers walk the tree. node is a *TreeNode. Assigning node = node.Left moves the pointer; it does not copy or change the tree.
    • Values, not nodes. The function receives p and q as int values, not as node pointers, so the comparisons use node.Val directly.
    • else if chains. Go's if needs no parentheses around the condition, but the braces are required, and else must sit on the same line as the closing brace of the previous block.
    • The final return -1. The compiler cannot know that the loop always returns early, so without a final return the function is rejected as missing one. The value -1 is a placeholder that does not appear in a valid run.
    • Nil children. If the walk reached a missing child, node would become nil and the loop would stop. With valid input that cannot happen.

    Complexity

    Time: O(h), where h is the height of the tree. The walk goes down one level per pass and never goes back. For a balanced tree that is about log n steps, and for a tree that is a single chain it is n.

    Space: O(1). Only the node pointer is kept, as the loop replaces recursion.

    Edge cases and common mistakes

    • One value is an ancestor of the other. For 2 and 4 the walk reaches the node 2: 4 is not smaller than 2, so neither "both smaller" nor "both larger" holds, and 2 is returned. No special case is needed.
    • Equal values. With p == q == 7 the walk goes right from 6, reaches 8, goes left to 7, and stops there because neither strict comparison holds.
    • Using <= or >=. Those would keep walking past a node whose value equals p or q and give a lower node than the correct answer.
    • The order of p and q. It does not matter: (8, 2) gives 6 just like (2, 8).
    • Treating it as a general binary tree. A solution that searches both children works, but it is O(n); it also ignores the BST order that this lesson uses.
    • The root is the answer. For 6 and 3 the first node is 6, equal to p, so it is returned at once.

    Testing

    On the tree from the overview:

    • p = 2, q = 8 gives 6.
    • p = 2, q = 4 gives 2.
    • p = 5, q = 3 gives 4.
    • p = 8, q = 2 gives 6.
    • p = 7, q = 7 gives 7.
    • p = 0, q = 5 gives 2.
    • p = 6, q = 3 gives 6.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free