Wikipedia contains a page on Tree Traversal that includes pseudo-codes for iterate over binary tree using cells. For example, this is the Pre-order Traversal :
iterativePreorder(node)
parentStack = empty stack
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
visit(node) #1
parentStack.push(node) #2
node = node.left
else
node = parentStack.pop() #3
node = node.right
I wrote down three points (# 1, # 2, # 3), which I will comment on later.
However, to solve the problem in question (LCA), not limiting to two descendants per node (binary tree), some adjustments are necessary:
An auxiliary stack to store the current child being visited at each level as the algorithm descends into the tree. Unlike a binary tree, where it is enough to go through the left node and then the right node to go through a node with n children we need a counter. And since each child can have m children, then there should be a counter for each level of the tree.
A second helper stack to store the path to the first node found. As one of the goals of the algorithm is to find two nodes, we must store the path to the first node and continue until we find the second.
A pseudo-code to find the ancestor closest to the nodes p and q , given the root node , looks like this:
findClosestCommonAncestor(node, p, q)
parentStack = empty stack
childIndexStack = empty stack
firstNodePath = null
while (not parentStack.isEmpty() or node ≠ null)
if (node ≠ null)
#1
if (node == p || node == q)
if (firstNodePath ≠ null)
parentStack.add(node)
int n = min(parentStack.length, firstNodePath.length)
for i = (n - 1)..0
if (parentStack(i) == firstNodePath(i))
return parentStack(i)
return null
else
firstNodePath = copy parentStack
firstNodePath.push(node)
#2
if (not empty node.children)
parentStack.push(node)
childIndexStack.push(0)
node = node.children(0)
else
node = null
else
#3
node = parentStack.peek()
i = childIndexStack.pop() + 1
if (i >= node.children.length)
node = null
parentStack.pop()
else
node = node.children(i)
childIndexStack.push(i)
It certainly got more complex, but the concept is basically the same as the previous one. Note that I also marked in this algorithm three points, because they are analogous to the previous one. Let's see:
-
# 1 This is the block where the value of the current node is processed. The
visit(node) of the first algorithm was replaced by a block that checks whether one of the nodes was found. If you have found the first node it saves the current stack. If you have found both, it compares the stacks, item by item, by looking for the nearest parent.
-
# 2 The initial algorithm adds the current node in the stack and advances to the child on the left. The second algorithm generalizes to
n children advancing to the first child (0).
-
# 3 The initial algorithm pops up a node and advances to the right child. The second algorithm generalizes by advancing to the next child (previous + 1).
The Java code looks like this:
class Node {
List<Node> children = new ArrayList<Node>();
Integer id;
Node(Integer id) {
this.id = id;
}
}
Node findClosestCommonAncestor(Node node, Node p, Node q) {
Stack<Node> parentStack = new Stack<Node>();
Stack<Integer> childIndexStack = new Stack<Integer>();
Stack<Node> firstNodePath = null;
while (!parentStack.empty() || node != null) {
if (node != null) {
if (node == p || node == q) {
if (firstNodePath != null) {
parentStack.add(node);
int n = Math.min(parentStack.size(), firstNodePath.size());
for (int i = n - 1; i >= 0; i--) {
if (parentStack.get(i) == firstNodePath.get(i)) {
return parentStack.get(i);
}
}
return null;
} else {
firstNodePath = new Stack<Node>();
firstNodePath.setSize(parentStack.size());
Collections.copy(firstNodePath, parentStack);
firstNodePath.push(node);
}
}
if (!node.children.isEmpty()) {
parentStack.push(node);
childIndexStack.push(0);
node = node.children.get(0);
} else {
node = null;
}
} else {
node = parentStack.peek();
Integer i = childIndexStack.pop() + 1;
if (i >= node.children.size()) {
node = null;
parentStack.pop();
} else {
node = node.children.get(i);
childIndexStack.push(i);
}
}
}
return null;
}
The full version of the Java code is available for editing and testing at ideone.com .
Update
In contrast to the statement proposed in the question, if there were information about the parent node and not the children, a much more efficient algorithm could be proposed.
Suppose that two nodes P and Q are given. This algorithm only needs:
Store P and their parents the nodes in a set C
Go through the parents of Q , starting from the element itself and returning the first element Q(i) that is in the C set.
Java code:
static class Node {
Node parent;
Integer id;
Node(Integer id, Node parent) {
this.id = id;
this.parent = parent;
}
public String toString() {
return id.toString();
}
}
static Node findClosestCommonAncestor(Node p, Node q) {
if (p == null || q == null) return null;
//guarda os pais do nó P, incluindo o próprio
Set<Node> parentsOfP = new HashSet<Node>();
while (p != null) {
parentsOfP.add(p);
p = p.parent;
}
//procura o primeiro pai de Q que está entre os pais de P
while (q != null) {
if (parentsOfP.contains(q)) {
return q;
}
q = q.parent;
}
return null;// not in the same tree
}
