AlgoDaily

Lowest Common Ancestor

Read at your own pace. Code execution, quizzes, progress tracking, and the AI tutor are available in the interactive view with JavaScript enabled.

Description

In the official React documentation, it's recommended that to find out where state data should live, the following steps be taken:

  • Identify every component that renders something based on that state.
  • Find a common owner component (a single component above all the components that need the state in the hierarchy).
  • Either the common owner or another component higher up in the hierarchy should own the state.

This is an algorithmic problem-- let's find the lowest common ancestor!

You're given a binary search tree tree1 and two of its child nodes as parameters. Can you write a method lowestCommonAncestor(root: Node, node1: Node, node2: Node) to identify the lowest common ancestor of the two nodes? The lowest common ancestor is the deepest node that has both of the two nodes as descendants.

In the below example, the lowest common ancestor of node 5 and 8 is 7.

/*
       7
      / \
     4   8
    / \
   1   5
*/

The method will called in the following manner: lowestCommonAncestor(root, node1, node2);.

You can assume our standard node definition for the tree vertices:

// Node definition
function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

# Node definition
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

Bonus: is there a way to find the lowest common ancestor of two nodes if the root wasn't passed as a parameter?

Constraints
  • Number of nodes in the BST <= 1000
  • The nodes will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(1) 
```js
function lowestCommonAncestor(root, node1, node2) {
  // Fill in this method
  return root;
}

function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

//       7
//      / \
//     4   8
//    / \
//   1  5

const root = new Node(7);
root.left = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(5);
root.right = new Node(8);

console.log(lowestCommonAncestor(root, 1, 8));
```

Step Two

The problem could be initially intimidating if you've never heard of the term lowest common ancestor. However, once you realize that it's just the highest shared parent that two nodes have in common, it's easy to visualize ways to use some form of traversal to our advantage.

One way to go about this problem is to visualize the traversal path required from the leaves. We'd probably want to move towards the top since that's where the ancestor is. In other words, we would follow the nodes upwards to get to the lowest common ancestor. This means if we wanted to find the LCA of 2 and 9 below, we'd first trace 2 upwards (so the path followed goes 2 -> 4 -> 6).

```js
/*
       6 
      / \ 
     4   9 
    / \
   2   5
  / \
 1   3
*/
```

Step Three

Then, we'd repeat this for 9 (9 -> 6).

See something in common? The final nodes of both paths ended up being the same (node 6). We are thus able to conclude that 6 is the lowest common ancestor, as it's by definition the highest node they have in common (note that there can more than one shared ancestor, but this is the lowest in the branching chain).

If we think about possible solutions, what do we need to do? The solution we want is a traversal to find the first difference in node-to-root path. Is there anything about BST properties that could help us traverse upwards while starting from the root?

Let's revisit some Binary Search Tree properties and start with a basic question about binary trees:

Multiple Choice

What is the name of the top-most node in a binary tree?

Step Five

Look at this BST, and let's say we're looking for 4 and 8's LCA:

```js
/*
   7
  / \
 4   8
*/
```

Step Six

From top to bottom, notice that 7 is between 4 and 8, as the structure follows the normal properties of a BST. We can express that idea with this conditional: if we encounter a node between node1 and node2, it means that it is a common ancestor of node1 and node2.

It also spawns these two ideas: if we encounter a node greater than both the nodes, we're going to find our lowest common ancestor on its left side. Likewise, if we encounter a node smaller than both the nodes, we're going to find our lowest common ancestor on its right side.

Why is that? Let's see the tree expanded a bit.

```js
/*
      7
     / \
    4   8
   / \
  1  5
*/
```

Step Seven

We'd like to find the LCA of 1 and 8. So start from 7, and compare 7 to 1 (greater) and 8 (less). It's in between, so we know it's the LCA!

What if we were looking to find the LCA of 1 and 5 instead?. Starting from 7, if we compare 7 to 1, it's greater. But 7 is ALSO greater than 5 -- it's greater than both.

That indicates that, from 7, we want to traverse left since we're currently to the right of both nodes.

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def least_common_ancestor(root, node_1, node_2):
    if root.val > node_1 and root.val > node_2:
        return least_common_ancestor(root.left, node_1, node_2)
    elif root.val < node_1 and root.val < node_2:
        return least_common_ancestor(root.right, node_1, node_2)
    else:
        return root

if __name__ == "__main__":
    root = TreeNode(6)
    root.left = TreeNode(2)
    root.right = TreeNode(8)
    root.left.left = TreeNode(0)
    root.left.right = TreeNode(4)
    root.right.left = TreeNode(7)
    root.right.right = TreeNode(9)
    print(least_common_ancestor(root, 2, 8).val)
```
```java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class Main {
    public static TreeNode leastCommonAncestor(TreeNode root, int node1, int node2) {
        if (root.val > node1 && root.val > node2) {
            return leastCommonAncestor(root.left, node1, node2);
        } else if (root.val < node1 && root.val < node2) {
            return leastCommonAncestor(root.right, node1, node2);
        } else {
            return root;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        System.out.println(leastCommonAncestor(root, 2, 8).val);
    }
}
```
```javascript
class TreeNode {
    constructor(val, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function leastCommonAncestor(root, node1, node2) {
    if (root.val > node1 && root.val > node2) {
        return leastCommonAncestor(root.left, node1, node2);
    } else if (root.val < node1 && root.val < node2) {
        return leastCommonAncestor(root.right, node1, node2);
    } else {
        return root;
    }
}

const root = new TreeNode(6);
root.left = new TreeNode(2);
root.right = new TreeNode(8);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(4);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);
console.log(leastCommonAncestor(root, 2, 8).val);
```
```cpp
#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* leastCommonAncestor(TreeNode* root, int node1, int node2) {
    if (root->val > node1 && root->val > node2) {
        return leastCommonAncestor(root->left, node1, node2);
    } else if (root->val < node1 && root->val < node2) {
        return leastCommonAncestor(root->right, node1, node2);
    } else {
        return root;
    }
}

int main() {
    TreeNode* root = new TreeNode(6);
    root->left = new TreeNode(2);
    root->right = new TreeNode(8);
    root->left->left = new TreeNode(0);
    root->left->right = new TreeNode(4);
    root->right->left = new TreeNode(7);
    root->right->right = new TreeNode(9);
    std::cout << leastCommonAncestor(root, 2, 8)->val << std::endl;
    return 0;
}
```
```csharp
class Program {
    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int x) { val = x; }
    }

    public static TreeNode LeastCommonAncestor(TreeNode root, int node1, int node2) {
        if (root.val > node1 && root.val > node2) {
            return LeastCommonAncestor(root.left, node1, node2);
        } else if (root.val < node1 && root.val < node2) {
            return LeastCommonAncestor(root.right, node1, node2);
        } else {
            return root;
        }
    }

    static void Main(string[] args) {
        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(2);
        root.right = new TreeNode(8);
        root.left.left = new TreeNode(0);
        root.left.right = new TreeNode(4);
        root.right.left = new TreeNode(7);
        root.right.right = new TreeNode(9);
        Console.WriteLine(LeastCommonAncestor(root, 2, 8).val);
    }
}
```
```go
package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func leastCommonAncestor(root *TreeNode, node1 int, node2 int) *TreeNode {
    if root.Val > node1 && root.Val > node2 {
        return leastCommonAncestor(root.Left, node1, node2)
    } else if root.Val < node1 && root.Val < node2 {
        return leastCommonAncestor(root.Right, node1, node2)
    } else {
        return root
    }
}

func main() {
    root := &TreeNode{Val: 6}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 8}
    root.Left.Left = &TreeNode{Val: 0}
    root.Left.Right = &TreeNode{Val: 4}
    root.Right.Left = &TreeNode{Val: 7}
    root.Right.Right = &TreeNode{Val: 9}
    fmt.Println(leastCommonAncestor(root, 2, 8).Val)
}
```

Step Eight

Here's how you could test out the previous code using another example input:

```python
class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def least_common_ancestor(root, node_1, node_2):
    if root.val > node_1 and root.val > node_2:
      return least_common_ancestor(root.left, node_1, node_2)
    elif root.val < node_1 and root.val < node_2:
      return least_common_ancestor(root.right, node_1, node_2)
    else:
        return root

#       7
#      / \
#     4   8
#    / \
#   1  5

root = Node(7)
root.left = Node(4)
root.left.left = Node(1)
root.left.right = Node(5)
root.right = Node(8)

print(least_common_ancestor(root, 1, 8).val)
```
```java
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public class Main {
    public static TreeNode leastCommonAncestor(TreeNode root, int node1, int node2) {
        if (root.val > node1 && root.val > node2) {
            return leastCommonAncestor(root.left, node1, node2);
        } else if (root.val < node1 && root.val < node2) {
            return leastCommonAncestor(root.right, node1, node2);
        } else {
            return root;
        }
    }

    public static void main(String[] args) {
        //       7
        //      / \
        //     4   8
        //    / \
        //   1  5

        TreeNode root = new TreeNode(7);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(8);

        System.out.println(leastCommonAncestor(root, 1, 8).val);
    }
}

```
```javascript
class Node {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function leastCommonAncestor(root, node1, node2) {
    if (root.val > node1 && root.val > node2) {
        return leastCommonAncestor(root.left, node1, node2);
    } else if (root.val < node1 && root.val < node2) {
        return leastCommonAncestor(root.right, node1, node2);
    } else {
        return root;
    }
}

//       7
//      / \
//     4   8
//    / \
//   1  5

const root = new Node(7);
root.left = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(5);
root.right = new Node(8);

console.log(leastCommonAncestor(root, 1, 8).val);
```
```cpp
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* leastCommonAncestor(TreeNode* root, int node1, int node2) {
    if (root->val > node1 && root->val > node2) {
        return leastCommonAncestor(root->left, node1, node2);
    } else if (root->val < node1 && root->val < node2) {
        return leastCommonAncestor(root->right, node1, node2);
    } else {
        return root;
    }
}

//       7
//      / \
//     4   8
//    / \
//   1  5

int main() {
    TreeNode* root = new TreeNode(7);
    root->left = new TreeNode(4);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(5);
    root->right = new TreeNode(8);

    std::cout << leastCommonAncestor(root, 1, 8)->val << std::endl;
}
```
```csharp
public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

public TreeNode LeastCommonAncestor(TreeNode root, int node1, int node2) {
    if (root.val > node1 && root.val > node2) {
        return LeastCommonAncestor(root.left, node1, node2);
    } else if (root.val < node1 && root.val < node2) {
        return LeastCommonAncestor(root.right, node1, node2);
    } else {
        return root;
    }
}

//       7
//      / \
//     4   8
//    / \
//   1  5

TreeNode root = new TreeNode(7);
root.left = new TreeNode(4);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(5);
root.right = new TreeNode(8);

Console.WriteLine(LeastCommonAncestor(root, 1, 8).val);
```
```go
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func leastCommonAncestor(root *TreeNode, node1 int, node2 int) *TreeNode {
    if root.Val > node1 && root.Val > node2 {
        return leastCommonAncestor(root.Left, node1, node2)
    } else if root.Val < node1 && root.Val < node2 {
        return leastCommonAncestor(root.Right, node1, node2)
    } else {
        return root
    }
}

//       7
//      / \
//     4   8
//    / \
//   1  5

func main() {
    root := &TreeNode{7, nil, nil}
    root.Left = &TreeNode{4, nil, nil}
    root.Left.Left = &TreeNode{1, nil, nil}
    root.Left.Right = &TreeNode{5, nil, nil}
    root.Right = &TreeNode{8, nil, nil}

    fmt.Println(leastCommonAncestor(root, 1, 8).Val)
}
```

Step Nine

We can alternatively use an iterative approach.

Order

Can you put these steps in the right order to iteratively find lowest common ancestor of two BST nodes?

Step Eleven

Let's put it all together:

```js
function lowestCommonAncestor(root, node1, node2) {
  // instantiate 2 arrays to keep track of paths
  const path1 = [];
  const path2 = [];

  // obtain the paths of each node from root
  if (!getPath(root, path1, node1) || !getPath(root, path2, node2)) {
    return false;
  }

  let i = 0;
  // compare the two until they differentiate or we hit the end
  while (i < path1.length && i < path2.length) {
    if (path1[i] != path2[i]) {
      break;
    }
    i++;
  }

  return path1[i - 1];

  function getPath(root, path, k) {
    if (!root) {
      return false;
    }

    // basic DFS
    path.push(root.val);

    if (root.val == k) {
      return true;
    }

    if (
      (root.left && getPath(root.left, path, k)) ||
      (root.right && getPath(root.right, path, k))
    ) {
      return true;
    }

    path.pop();
    return false;
  }
}

function Node(val) {
  this.val = val;
  this.left = this.right = null;
}

//       7
//      / \
//     4   8
//    / \
//   1  5

const root = new Node(7);
root.left = new Node(4);
root.left.left = new Node(1);
root.left.right = new Node(5);
root.right = new Node(8);

console.log(lowestCommonAncestor(root, 1, 8));
```
```java
class Node {
    int val;
    Node left;
    Node right;
    public Node(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

public class Main {
    public static int lowestCommonAncestor(Node root, int node1, int node2) {
        ArrayList<Integer> path1 = new ArrayList<>();
        ArrayList<Integer> path2 = new ArrayList<>();

        if (!getPath(root, path1, node1) || !getPath(root, path2, node2)) {
            return -1; // or any other indication of failure
        }

        int i = 0;
        while (i < path1.size() && i < path2.size()) {
            if (!path1.get(i).equals(path2.get(i))) {
                break;
            }
            i++;
        }

        return path1.get(i - 1);
    }

    public static boolean getPath(Node root, ArrayList<Integer> path, int k) {
        if (root == null) {
            return false;
        }

        path.add(root.val);

        if (root.val == k) {
            return true;
        }

        if ((root.left != null && getPath(root.left, path, k)) || (root.right != null && getPath(root.right, path, k))) {
            return true;
        }

        path.remove(path.size() - 1);
        return false;
    }

    public static void main(String[] args) {
        Node root = new Node(7);
        root.left = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(5);
        root.right = new Node(8);

        System.out.println(lowestCommonAncestor(root, 1, 8));
    }
}
```
```python
class Node:
    def __init__(self, val):
        self.val = val
        self.left = self.right = None

def lowest_common_ancestor(root, node1, node2):
    path1 = []
    path2 = []

    if not get_path(root, path1, node1) or not get_path(root, path2, node2):
        return False

    i = 0
    while i < len(path1) and i < len(path2):
        if path1[i] != path2[i]:
            break
        i += 1

    return path1[i - 1]

def get_path(root, path, k):
    if not root:
        return False

    path.append(root.val)

    if root.val == k:
        return True

    if (root.left and get_path(root.left, path, k)) or (root.right and get_path(root.right, path, k)):
        return True

    path.pop()
    return False

root = Node(7)
root.left = Node(4)
root.left.left = Node(1)
root.left.right = Node(5)
root.right = Node(8)

print(lowest_common_ancestor(root, 1, 8))
```
```cpp
#include <vector>
#include <iostream>

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int val) : val(val), left(nullptr), right(nullptr) {}
};

bool getPath(Node* root, std::vector<int>& path, int k) {
    if (!root) return false;

    path.push_back(root->val);

    if (root->val == k) return true;

    if ((root->left && getPath(root->left, path, k)) || (root->right && getPath(root->right, path, k))) {
        return true;
    }

    path.pop_back();
    return false;
}

int lowestCommonAncestor(Node* root, int node1, int node2) {
    std::vector<int> path1, path2;

    if (!getPath(root, path1, node1) || !getPath(root, path2, node2)) {
        return -1; // or any other indication of failure
    }

    int i = 0;
    while (i < path1.size() && i < path2.size()) {
        if (path1[i] != path2[i]) {
            break;
        }
        i++;
    }

    return path1[i - 1];
}

int main() {
    Node* root = new Node(7);
    root->left = new Node(4);
    root->left->left = new Node(1);
    root->left->right = new Node(5);
    root->right = new Node(8);

    std::cout << lowestCommonAncestor(root, 1, 8) << std::endl;
}
```
```csharp
using System;
using System.Collections.Generic;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
        this.left = this.right = null;
    }
}

class MainClass {
    public static bool GetPath(Node root, List<int> path, int k) {
        if (root == null) return false;

        path.Add(root.val);

        if (root.val == k) return true;

        if ((root.left != null && GetPath(root.left, path, k)) || (root.right != null && GetPath(root.right, path, k))) {
            return true;
        }

        path.RemoveAt(path.Count - 1);
        return false;
    }

    public static int LowestCommonAncestor(Node root, int node1, int node2) {
        List<int> path1 = new List<int>();
        List<int> path2 = new List<int>();

        if (!GetPath(root, path1, node1) || !GetPath(root, path2, node2)) {
            return -1; // or any other indication of failure
        }

        int i = 0;
        while (i < path1.Count && i < path2.Count) {
            if (path1[i] != path2[i]) {
                break;
            }
            i++;
        }

        return path1[i - 1];
    }

    public static void Main(string[] args) {
        Node root = new Node(7);
        root.left = new Node(4);
        root.left.left = new Node(1);
        root.left.right = new Node(5);
        root.right = new Node(8);

        Console.WriteLine(LowestCommonAncestor(root, 1, 8));
    }
}
```
```go
package main

import "fmt"

type Node struct {
    Val   int
    Left  *Node
    Right *Node
}

func getPath(root *Node, path *[]int, k int) bool {
    if root == nil {
        return false
    }

    *path = append(*path, root.Val)

    if root.Val == k {
        return true
    }

    if (root.Left != nil && getPath(root.Left, path, k)) || (root.Right != nil && getPath(root.Right, path, k)) {
        return true
    }

    *path = (*path)[:len(*path)-1]
    return false
}

func lowestCommonAncestor(root *Node, node1 int, node2 int) int

 {
    path1 := []int{}
    path2 := []int{}

    if !getPath(root, &path1, node1) || !getPath(root, &path2, node2) {
        return -1 // or any other indication of failure
    }

    i := 0
    for i < len(path1) && i < len(path2) {
        if path1[i] != path2[i] {
            break
        }
        i++
    }

    return path1[i-1]
}

func main() {
    root := &Node{7, nil, nil}
    root.Left = &Node{4, nil, nil}
    root.Left.Left = &Node{1, nil, nil}
    root.Left.Right = &Node{5, nil, nil}
    root.Right = &Node{8, nil, nil}

    fmt.Println(lowestCommonAncestor(root, 1, 8))
}
```

One Pager Cheat Sheet

One Pager Cheat Sheet

  • Identify the lowestCommonAncestor of two nodes by finding the common owner component in the hierarchy with an algorithmic O(n) time complexity and O(1) space complexity.
  • Finding the lowest common ancestor of two given nodes is as simple as tracing their paths upwards until the highest shared parent is reached.
  • The "lowest common ancestor" of two nodes can be found by traversing upwards from the root in a BST to find the first difference in node-to-root paths.
  • The binary tree has exactly one root which is the top-most node and connects to all other nodes in the tree, creating a hierarchical pyramid-like structure.
  • The Lowest Common Ancestor of 4 and 8 in this Binary Search Tree can be easily identified.
  • If we traverse a BST and encounter a node between two other nodes, it is the lowest common ancestor of those two nodes, and whichever side its value is on will reveal which side of it the lowest common ancestor is found.
  • We can find the Lowest Common Ancestor of two nodes by comparing the node we're on to the nodes we're looking for, and traversing left or right accordingly to get closer to the LCA.
  • Run previous code with sample data to verify results.
  • An iterative approach can be used alternatively.
  • By using Pre-order DFS traversal to populate two arrays with the paths from each node to the root, the first different node in the paths can be easily identified as the Lowest Common Ancestor of the two nodes.
  • Creating a successful marketing strategy requires an in-depth understanding of customer needs, current market trends and innovative tactics.
Open interactive view →