1650. Lowest Common Ancestor of a Binary Tree III


Problem Description

In this problem, we are given a binary tree where each node not only has references to its left and right children but also a reference to its parent node. We need to find the lowest common ancestor (LCA) of two given nodes in this binary tree. By definition, the LCA is the deepest node that is an ancestor to both nodes. To clarify, a node can be an ancestor to itself according to this problem's definition.

Intuition

The intuition behind the solution to finding the lowest common ancestor (LCA) relies on a simple observation: If we traverse the tree starting from nodes p and q upwards towards the root by following parent references, the paths will eventually intersect at some node - this node will be the LCA. By traveling up through the parent nodes, both paths must either converge at the LCA or at the root of the tree.

However, since p and q might not be at the same depth (distance from the root), simply moving upwards will not guarantee that they meet at the LCA. To address this, the solution uses two pointers a and b, initially pointing to p and q. They move upwards synchronously by following the parent references. However, if any pointer reaches the root (where the parent reference is None) without finding the LCA, it switches to point at the other node (a to q and b to p). This pointer switch effectively aligns the traversal paths of p and q such that after a complete cycle (root to the other node and up again), the paths have the same length, ensuring that a and b will meet at the LCA.

Learn more about Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of the following problems can be solved with backtracking (select multiple)

Solution Approach

To implement the solution for finding the lowest common ancestor, the approach uses two pointers and takes advantage of the parent reference in each node. The algorithm does not require additional data structures or complex patterns - it's a straightforward loop with a condition that exploits the structure of the binary tree.

Here is a step-by-step walkthrough of the implementation:

  1. Initialize two pointers, a and b, both pointing to the given nodes p and q, respectively.
  2. Enter a loop that continues until the pointers meet (a == b), which would indicate that the LCA has been found.
  3. In each iteration of the loop, move each pointer to its parent. However, when a pointer would move to a None reference (indicating it has reached the root), it switches to the other node:
    • Pointer a moves to a.parent if a has a parent, otherwise it switches to point at q.
    • Pointer b moves to b.parent if b has a parent, otherwise it switches to point at p.
  4. The loop exits when a and b meet, meaning the LCA has been found. Since we switch pointers when we reach the root, both pointers traverse a path that is equal to the sum of the lengths of the paths from p to the root and from q to the root. Therefore, they are guaranteed to meet at the LCA.

This implementation ensures that both pointers traverse the same total path length, which means they will intersect at the LCA, not before, no matter their initial positions in the tree.

Here is how the code from the Reference Solution Approach embodies the described algorithm:

1class Solution:
2    def lowestCommonAncestor(self, p: 'Node', q: 'Node') -> 'Node':
3        a, b = p, q
4        while a != b:
5            a = a.parent if a.parent else q
6            b = b.parent if b.parent else p
7        return a

The while loop represents the traversal and meeting point discovery, and the condition within the loop handles the pointer switching logic. The resultant a (or b, since they're equal when the loop exits) is returned as the LCA of nodes p and q.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the following is a min heap?

Example Walkthrough

Consider this simple binary tree as our example:

1      1
2     / \
3    2   3
4   / \
5  4   5

Node 1 is the root of the tree. Each node except the root has a parent reference. We want to find the lowest common ancestor (LCA) of nodes 4 and 5. According to the problem statement, node 2 is an ancestor of both 4 and 5 and is the lowest one, so it is our expected answer.

Let's walk through the solution approach step-by-step:

  1. We initialize two pointers: a points to node 4 and b points to node 5.
  2. We enter the loop:
    1. Both pointers a and b start moving upwards. For the first iteration:
      • Pointer a moves to its parent, which is node 2.
      • Pointer b moves to its parent, which is also node 2.
    2. Now, a and b both point to the same node (node 2), the loop condition a != b is not satisfied, and thus we exit the loop.
  3. Pointer a (or b, since they point to the same node) now points to node 2, which is indeed the LCA of nodes 4 and 5.

The pointers met at node 2 without needing to switch to point at the other node, as nodes 4 and 5 are at the same depth. However, if we were to find the LCA of nodes 4 and 3, the switch would occur because the initial paths from nodes 4 and 3 to the root are of different lengths.

As a result, the algorithm works as expected, and we return node 2 as the LCA for nodes 4 and 5.

Solution Implementation

1class Node:
2    def __init__(self, val):
3        self.val = val
4        self.left = None
5        self.right = None
6        self.parent = None
7
8
9class Solution:
10    def lowestCommonAncestor(self, node_p: 'Node', node_q: 'Node') -> 'Node':
11        """Find the lowest common ancestor of two nodes in a binary tree with parent pointers.
12      
13        Args:
14            node_p (Node): The first node.
15            node_q (Node): The second node.
16          
17        Returns:
18            Node: The lowest common ancestor of node_p and node_q.
19        """
20        # Start both pointers at the given nodes.
21        pointer_a = node_p
22        pointer_b = node_q
23      
24        # Continue traversing up the tree until both pointers meet at the common ancestor.
25        while pointer_a != pointer_b:
26            # If pointer_a has a parent, move to the parent; otherwise, go to the other node's initial position.
27            pointer_a = pointer_a.parent if pointer_a.parent else node_q
28          
29            # Do the same for pointer_b, going to the initial position of node_p if there's no parent.
30            pointer_b = pointer_b.parent if pointer_b.parent else node_p
31      
32        # Once they meet, that's the lowest common ancestor.
33        return pointer_a
34
1class Solution {
2    // This method finds the lowest common ancestor (LCA) of two nodes in a binary tree where nodes have parent pointers.
3    public Node lowestCommonAncestor(Node firstNode, Node secondNode) {
4        // Initialize two pointers for traversing the ancestors of the given nodes.
5        Node pointerA = firstNode;
6        Node pointerB = secondNode;
7
8        // Traverse the ancestor chain of both nodes until they meet.
9        while (pointerA != pointerB) {
10            // If pointerA has reached the root (parent is null), start it at secondNode,
11            // otherwise, move it to its parent.
12            pointerA = pointerA.parent == null ? secondNode : pointerA.parent;
13          
14            // If pointerB has reached the root (parent is null), start it at firstNode,
15            // otherwise, move it to its parent.
16            pointerB = pointerB.parent == null ? firstNode : pointerB.parent;
17        }
18
19        // When pointerA and pointerB meet, we have found the LCA.
20        return pointerA;
21    }
22}
23
1// Definition for a Node provided by the problem statement.
2class Node {
3public:
4    int value;        // The integer value held by the node.
5    Node* left;       // Pointer to the left child of the node.
6    Node* right;      // Pointer to the right child of the node.
7    Node* parent;     // Pointer to the parent of the node.
8};
9
10class Solution {
11public:
12    // Function to find the lowest common ancestor of two nodes in a binary tree with parent pointers.
13    Node* lowestCommonAncestor(Node* firstNode, Node* secondNode) {
14        // Create pointers to traverse the ancestor hierarchy of each node.
15        Node* currentFirst = firstNode;
16        Node* currentSecond = secondNode;
17
18        // Continue looping until the two pointers meet at the lowest common ancestor.
19        while (currentFirst != currentSecond) {
20            // If currentFirst has a parent, move up the tree, otherwise, jump to secondNode.
21            currentFirst = currentFirst->parent ? currentFirst->parent : secondNode;
22            // If currentSecond has a parent, move up the tree, otherwise, jump to firstNode.
23            currentSecond = currentSecond->parent ? currentSecond->parent : firstNode;
24        }
25        // When currentFirst and currentSecond meet, we've found the lowest common ancestor.
26        return currentFirst;
27    }
28};
29
1// Type definition for a Node within a binary tree.
2type Node = {
3  value: number;   // The integer value held by the node.
4  left: Node | null;   // Reference to the left child of the node, if any.
5  right: Node | null;  // Reference to the right child of the node, if any.
6  parent: Node | null; // Reference to the parent of the node, if any.
7};
8
9// Function to find the lowest common ancestor (LCA) of two nodes in a binary tree.
10// The tree structure includes parent pointers.
11function lowestCommonAncestor(firstNode: Node | null, secondNode: Node | null): Node | null {
12  // Initialize pointers to traverse the ancestor hierarchy starting from each node.
13  let currentFirst: Node | null = firstNode;
14  let currentSecond: Node | null = secondNode;
15
16  // Iterate until the two pointers meet at the LCA.
17  while (currentFirst !== currentSecond) {
18    // If currentFirst has a parent, move up the hierarchy, otherwise go to secondNode's position.
19    currentFirst = currentFirst && currentFirst.parent ? currentFirst.parent : secondNode;
20    // If currentSecond has a parent, move up the hierarchy, otherwise go to firstNode's position.
21    currentSecond = currentSecond && currentSecond.parent ? currentSecond.parent : firstNode;
22  }
23  // When currentFirst === currentSecond, we've found the LCA.
24  return currentFirst;
25}
26
27// Example usage:
28// Assuming there exists an established binary tree with parent pointers and two nodes, nodeA and nodeB.
29// let lca = lowestCommonAncestor(nodeA, nodeB);
30
Not Sure What to Study? Take the 2-min Quiz:

Which type of traversal does breadth first search do?

Time and Space Complexity

The given Python function finds the lowest common ancestor (LCA) of two nodes in a binary tree where nodes have a pointer to their parent.

Time Complexity:

The time complexity of the code is O(h) where h is the height of the tree. This is because, in the worst case, both nodes p and q could be at the bottom of the tree, and we would traverse from each node up to the root before finding the LCA. Since we are moving at most up to the height of the tree for both p and q, the time complexity remains O(h).

Space Complexity:

The space complexity of the code is O(1). This is due to the fact that we are only using a fixed number of pointers (a and b) regardless of the size of the input tree, and no additional data structures or recursive stack space are used.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫