Wikipedia contains a page about Tree Traversal which includes pseudo-codes to iterate over binary tree using stacks. For example, this is from 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 being limited to two descendants per node (binary tree), some adjustments are necessary:
- An auxiliary stack to store the current child being visited at each level that the algorithm goes down in the tree. Different from a binary tree, where you just go through the left node and then the right node, to go through a node with
n children we need an accountant. And how each child can have m children, then there should be a counter for each level of the tree.
- A second auxiliary battery to store the way up to the first node found. As one of the objectives of the algorithm is to find two nodes, we must store the path to the first and continue until we find the second.
A pseudo-code to find the closest ancestor to the nodes p and q, given the root node, was 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 became more complex, but the concept is basically the same as the previous one. Note that I also marked in this algorithm three points, as they are analogous to the previous one. Let’s see:
- #1 This is the block where the value of the current node is processed. O
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 found both, you compare the stacks, item by item, looking for the nearest parent.
- #2 The initial algorithm adds the current node on the stack and advances to the left child. The second algorithm generalizes to
n Children advancing to the first child (0).
- #3 The initial algorithm pops a node and advances to the right child. The second algorithm generalizes by advancing to the next child (previous + 1).
The code in Java looked 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 Java code is available for editing and testing on ideone..
Updating
Contrary to the statement proposed in the question, if there was information of the parent node and not of the children, a much more efficient algorithm could be proposed.
Suppose you are given two nodes P and Q. This algorithm just needs:
- Store
P and their parents us in one set C
- Walk through the parents of
Q, starting from the element itself and returning the first element Q(i) that is in the set C.
Code in Java:
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
}
Do your nodes have references to the father? This is not clear in the question (I did not read the reference in the OS). If not, my answer below does not apply...
– mgibsonbr
Unfortunately the problem at hand usually does not have this information. Obviously the algorithm could have an additional step to go through the tree and store this information. I’ve actually solved it that way, that is, dividing it into steps, but I’m looking for a more refined algorithm.
– utluiz