Grind 75 Question 11: Lowest Common Ancestor of a Binary Tree
The…what now?
The 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).”
Help.
The Initial Attempts
I can do this. I can do this. I’ve traversed a binary tree before! NBD. The first step is to truly understand what the problem is asking of me. Ah, okay. Find the node that is the ancestor of both given nodes — the one that’s higher up on the tree that touches both given nodes. Got it. So. To the whiteboard.
I don’t get very far before I realize I. Need. Halp. No shame in admitting it. Off to Neetcode I go. (Here’s my code so you can laugh at me:)
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
commonAncestor = root;
while(root){
if (root.left == p || root.right == p || root.left == q || root.right == q){
console.log("Found it");
}
root = root.next;
}
return commonAncestor;
};I will say, I think the solution will implement a depth-first search and involve recursion. So let’s just see how right (or wrong) I am.
The Solution
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @param {TreeNode} p
* @param {TreeNode} q
* @return {TreeNode}
*/
var lowestCommonAncestor = function(root, p, q) {
let commonAncestor = root;
while(commonAncestor){
if (p.val < commonAncestor.val && q.val < commonAncestor.val) {
commonAncestor = commonAncestor.left;
}
else if (p.val > commonAncestor.val && q.val > commonAncestor.val) {
commonAncestor = commonAncestor.right;
}
else return commonAncestor;
}
return commonAncestor;
};So…I was not exactly correct with either of my guesses. But I learned more about binary trees, so it’s a win!
Here’s what the code above does:
- Since we’re returning the common ancestor, we declare it as a new variable. (Unnecessary? I’m not sure. Yep, on refactoring, you can just do this by manipulating root.)
- So the next thing you do is a while loop — while there is root to be looked at (which there always will be, until you’re ready to return):
- If the P and Q are both smaller than the node that’s currently the root, go a level deeper to the left. Since binary trees are (apparently!) populated in order, there’s no need to search the right half of the tree if the numbers are both smaller than the root. Everything to the right of the root will be larger.
- If the P and Q are both larger than the node that’s currently the root, go a level deeper to the right. See above, but replace right with left.
- If none of those conditions apply, you know that the two numbers share the root node being looked at, so ba-boom! Return the root. O(log n) time complexity.
What I Learned
- First off, the bit about binary trees being numbered in order; that is, the value of the root node will always be between the right and left. Helpful to know!
- Second, .val is very important. I tried tweaking the solution to not include p.val or q.val (just p or q) and it failed. The more you know, right?
mins
read
