Solutions

1. Brute Force

O(n²) time | O(1) space

Intuition

We can take every ancestor of p and check it against every ancestor of q with two nested loops.

Algorithm

Traverse through all the ancestors of p.
For each step, traverse through all the ancestors of q and return the first common node.

p q

4 != 6

1 / 9

Code

# Definitions:
# class Node:
#     def __init__(self, val=0, children=None, parent=None):
#         self.val = val
#         self.children = children if children is not None else []
#         self.parent = parent

def lowestCommonAncestor(p: Node, q: Node) -> Node:
    current_p = p
    while current_p:
        current_q = q
        while current_q:
            if current_p is current_q:
                return current_p
            current_q = current_q.parent
        current_p = current_p.parent
    return None

// Definitions:
// function Node(val, children, parent) {
//     this.val = val
//     this.children = children || []
//     this.parent = parent || null
// }

/**
 * @param {Node} p
 * @param {Node} q
 * @returns {Node}
 */
var lowestCommonAncestor = function (p, q) {
  let currentP = p
  while (currentP) {
    let currentQ = q
    while (currentQ) {
      if (currentP === currentQ) return currentP
      currentQ = currentQ.parent
    }
    currentP = currentP.parent
  }
  return null
}

// Definitions:
// class Node {
//     int val;
//     java.util.List<Node> children = new java.util.ArrayList<>();
//     Node parent;
//
//     Node() {}
//
//     Node(int val) {
//         this.val = val;
//     }
// }

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node currentP = p;
        while (currentP != null) {
            Node currentQ = q;
            while (currentQ != null) {
                if (currentP == currentQ) return currentP;
                currentQ = currentQ.parent;
            }
            currentP = currentP.parent;
        }
        return null;
    }
}

2. Hash Table

O(n) time | O(n) space

Intuition

We can first traverse through all the ancestors of p and put them into a hash set.

Then traverse through all the ancestors of q and return the first one that is in the hash set.

Algorithm

Create an empty hash set.
Traverse through all the ancestors of p, adding every ancestor to the hash set.
Traverse through all the ancestors of q and return the first one that is in the hash set.

p q

seen

Put 4 in the hash set

1 / 7

Code

# Definitions:
# class Node:
#     def __init__(self, val=0, children=None, parent=None):
#         self.val = val
#         self.children = children if children is not None else []
#         self.parent = parent

def lowestCommonAncestor(p: Node, q: Node) -> Node:
    seen = set()
    current_p = p
    while current_p:
        seen.add(current_p)
        current_p = current_p.parent
    current_q = q
    while current_q:
        if current_q in seen:
            return current_q
        current_q = current_q.parent
    return None

// Definitions:
// function Node(val, children, parent) {
//     this.val = val
//     this.children = children || []
//     this.parent = parent || null
// }

/**
 * @param {Node} p
 * @param {Node} q
 * @returns {Node}
 */
var lowestCommonAncestor = function (p, q) {
  const seen = new Set()
  let currentP = p
  while (currentP) {
    seen.add(currentP)
    currentP = currentP.parent
  }
  let currentQ = q
  while (currentQ) {
    if (seen.has(currentQ)) return currentQ
    currentQ = currentQ.parent
  }
  return null
}

// Definitions:
// class Node {
//     int val;
//     java.util.List<Node> children = new java.util.ArrayList<>();
//     Node parent;
//
//     Node() {}
//
//     Node(int val) {
//         this.val = val;
//     }
// }

import java.util.HashSet;
import java.util.Set;

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Set<Node> seen = new HashSet<>();
        Node currentP = p;
        while (currentP != null) {
            seen.add(currentP);
            currentP = currentP.parent;
        }
        Node currentQ = q;
        while (currentQ != null) {
            if (seen.contains(currentQ)) return currentQ;
            currentQ = currentQ.parent;
        }
        return null;
    }
}

3. Depth Alignment

O(n) time | O(1) space

Intuition

If both nodes were at the same depth, we could traverse both nodes' ancestors at the same time with one loop and they would meet at the lowest common ancestor.

To align the depths, we can count each depth first and move the deeper node up by the difference.

Algorithm

Traverse through all the ancestors of p, counting the steps into p_depth.
Traverse through all the ancestors of q, counting the steps into q_depth.
Move the deeper node up by the difference between p_depth and q_depth, so both of them start at the same depth.
Traverse through both nodes' ancestors at the same time until they meet.
Return the node both of them are on.

p q

depth = 1

1 / 12

Code

# Definitions:
# class Node:
#     def __init__(self, val=0, children=None, parent=None):
#         self.val = val
#         self.children = children if children is not None else []
#         self.parent = parent

def lowestCommonAncestor(p: Node, q: Node) -> Node:
    p_depth, q_depth = depth(p), depth(q)
    current_p = lift(p, max(p_depth - q_depth, 0))
    current_q = lift(q, max(q_depth - p_depth, 0))
    while current_p is not current_q:
        current_p = current_p.parent
        current_q = current_q.parent
    return current_p


def depth(node):
    steps = 0
    while node:
        steps += 1
        node = node.parent
    return steps


def lift(node, steps):
    for _ in range(steps):
        node = node.parent
    return node

// Definitions:
// function Node(val, children, parent) {
//     this.val = val
//     this.children = children || []
//     this.parent = parent || null
// }

/**
 * @param {Node} p
 * @param {Node} q
 * @returns {Node}
 */
var lowestCommonAncestor = function (p, q) {
  const pDepth = depth(p)
  const qDepth = depth(q)
  let currentP = lift(p, Math.max(pDepth - qDepth, 0))
  let currentQ = lift(q, Math.max(qDepth - pDepth, 0))
  while (currentP !== currentQ) {
    currentP = currentP.parent
    currentQ = currentQ.parent
  }
  return currentP
}

function depth(node) {
  let steps = 0
  while (node) {
    steps++
    node = node.parent
  }
  return steps
}

function lift(node, steps) {
  for (let i = 0; i < steps; i++) node = node.parent
  return node
}

// Definitions:
// class Node {
//     int val;
//     java.util.List<Node> children = new java.util.ArrayList<>();
//     Node parent;
//
//     Node() {}
//
//     Node(int val) {
//         this.val = val;
//     }
// }

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        int pDepth = depth(p);
        int qDepth = depth(q);
        Node currentP = lift(p, Math.max(pDepth - qDepth, 0));
        Node currentQ = lift(q, Math.max(qDepth - pDepth, 0));
        while (currentP != currentQ) {
            currentP = currentP.parent;
            currentQ = currentQ.parent;
        }
        return currentP;
    }

    private int depth(Node node) {
        int steps = 0;
        while (node != null) {
            steps++;
            node = node.parent;
        }
        return steps;
    }

    private Node lift(Node node, int steps) {
        for (int i = 0; i < steps; i++) node = node.parent;
        return node;
    }
}

4. Two Pointers

O(n) time | O(1) space

Intuition

We can traverse both nodes' ancestors at the same time with one loop.

When the pointer of p's ancestors reaches the root, we put it on q, and when the pointer of q's ancestors reaches the root, we put it on p.

Then both pointers go through the same number of steps (depth of p + depth of q), so they meet at the lowest common ancestor.

Algorithm

Create current_p and current_q pointer variables with p and q as initial values.
Traverse through both nodes' ancestors at the same time while current_p and current_q are not the same node.
- Move current_p to its parent, or to q if current_p is the root.
- Move current_q to its parent, or to p if current_q is the root.
Return current_p.

current_p current_q

4 != 6

1 / 7

Code

# Definitions:
# class Node:
#     def __init__(self, val=0, children=None, parent=None):
#         self.val = val
#         self.children = children if children is not None else []
#         self.parent = parent

def lowestCommonAncestor(p: Node, q: Node) -> Node:
    current_p, current_q = p, q
    while current_p is not current_q:
        current_p = current_p.parent or q
        current_q = current_q.parent or p
    return current_p

// Definitions:
// function Node(val, children, parent) {
//     this.val = val
//     this.children = children || []
//     this.parent = parent || null
// }

/**
 * @param {Node} p
 * @param {Node} q
 * @returns {Node}
 */
var lowestCommonAncestor = function (p, q) {
  let currentP = p
  let currentQ = q
  while (currentP !== currentQ) {
    currentP = currentP.parent || q
    currentQ = currentQ.parent || p
  }
  return currentP
}

// Definitions:
// class Node {
//     int val;
//     java.util.List<Node> children = new java.util.ArrayList<>();
//     Node parent;
//
//     Node() {}
//
//     Node(int val) {
//         this.val = val;
//     }
// }

class Solution {
    public Node lowestCommonAncestor(Node p, Node q) {
        Node currentP = p;
        Node currentQ = q;
        while (currentP != currentQ) {
            currentP = currentP.parent == null ? q : currentP.parent;
            currentQ = currentQ.parent == null ? p : currentQ.parent;
        }
        return currentP;
    }
}