Lowest Common Ancestor of a Binary Tree III

Lowest Common Ancestor of a Binary Tree III - Problem

Given two nodes p and q of a binary tree, return their lowest common ancestor (LCA).

Each node will have a reference to its parent node. The definition for Node is below:

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
}

According to the definition of LCA on Wikipedia: "The lowest common ancestor of two nodes p and q in a tree T is the lowest node that has both p and q as descendants (where we allow a node to be a descendant of itself)."

Input & Output

Example 1 — Basic Tree Structure

$ Input: Tree: [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1

› Output: 3

💡 Note: The LCA of nodes 5 and 1 is 3. Node 3 is the lowest node that has both 5 and 1 as descendants.

Example 2 — One Node is Ancestor

$ Input: Tree: [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4

› Output: 5

💡 Note: The LCA of nodes 5 and 4 is 5. Since node 4 is a descendant of node 5, node 5 is their lowest common ancestor.

Example 3 — Same Node

$ Input: Tree: [1,2], p = 1, q = 1

› Output: 1

💡 Note: The LCA of a node with itself is the node itself.

Constraints

The number of nodes in the tree is in the range [2, 10⁵]
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique
p != q
p and q exist in the tree

Visualization

Tap to expand

Understanding the Visualization

Input

Binary tree with parent pointers and two target nodes p and q

Process

Use parent pointers to traverse upward from both nodes

Output

Return the lowest node that is ancestor of both p and q

Key Takeaway

🎯 Key Insight: Parent pointers transform tree LCA into a linked list intersection problem

Asked in

f Facebook 45 M Microsoft 35 a Amazon 30 G Google 25

The key insight is that with parent pointers, we can treat this like a linked list intersection problem. The optimal two pointers approach uses O(1) space by having two pointers traverse upward and redirect when reaching null. Time: O(h), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers Intersection	O(h)	O(1)	Use two pointers traversing upward simultaneously, like finding intersection of two linked lists
Hash Set Path Storage	O(h)	O(h)	Store all ancestors of one node, then traverse ancestors of other node until we find a match

Two Pointers Intersection — Algorithm Steps

Step 1: Initialize two pointers at p and q
Step 2: Move both pointers upward to parents
Step 3: When pointer reaches null, redirect to other starting node
Step 4: Pointers meet at LCA

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start two pointers at p and q

Traverse Up

Move pointers to parents, redirect when reaching null

Meet at LCA

Pointers converge at lowest common ancestor

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct Node {
    int val;
    struct Node* left;
    struct Node* right;
    struct Node* parent;
};

struct Node* solution(struct Node* p, struct Node* q) {
    struct Node* a = p;
    struct Node* b = q;
    
    // Continue until they meet
    while (a != b) {
        // When a reaches null, redirect to q
        // When b reaches null, redirect to p
        a = a ? a->parent : q;
        b = b ? b->parent : p;
    }
    
    return a;
}

struct Node* createNode(int val) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}

int main() {
    // Simple implementation for demonstration
    struct Node* root = createNode(3);
    struct Node* node5 = createNode(5);
    struct Node* node1 = createNode(1);
    struct Node* node6 = createNode(6);
    struct Node* node2 = createNode(2);
    struct Node* node0 = createNode(0);
    struct Node* node8 = createNode(8);
    struct Node* node7 = createNode(7);
    struct Node* node4 = createNode(4);
    
    root->left = node5;
    root->right = node1;
    node5->parent = root;
    node1->parent = root;
    
    node5->left = node6;
    node5->right = node2;
    node6->parent = node5;
    node2->parent = node5;
    
    node1->left = node0;
    node1->right = node8;
    node0->parent = node1;
    node8->parent = node1;
    
    node2->left = node7;
    node2->right = node4;
    node7->parent = node2;
    node4->parent = node2;
    
    struct Node* result = solution(node5, node1);
    printf("%d\n", result->val);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(h)

Each pointer traverses at most 2h nodes, where h is the height of the tree

✓ Linear Growth

Space Complexity

O(1)

Only two pointer variables used, no extra data structures

✓ Linear Space

89.3K Views

Medium Frequency

~15 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers Intersection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler