tree walking -- saved recursion state

[Mikito Harakiri]

I have a tree modeled like this

class Node {
private Vector children = new Vector(); //
children.elementAt(i).getType() == Node.class
private Node parent = null;
}

I want to write a method nextLeaf(). It's very easy to write a Node's method
that makes recursive depth-first enumeration:

public void walkSubTree() {
for( int i = 0; i < children.size(); i++ )
walkSubTree(children.elementAt(i));
}

Now, I wonder how can I reconciliate recursive nature of "server" function
walkSubTree() with a "client" function nextLeaf() need to receive nodes
supplied by walkSubTree() in a "discontinous" manner. If after finding a
leaf could I save the recursion state somehow...

 

[Robert Olofsson]

: class Node {
: private Vector children = new Vector(); //
: children.elementAt(i).getType() == Node.class
: private Node parent = null;
: }
: ...
: Now, I wonder how can I reconciliate recursive nature of "server" function
: walkSubTree() with a "client" function nextLeaf() need to receive nodes
: supplied by walkSubTree() in a "discontinous" manner. If after finding a
: leaf could I save the recursion state somehow...

If I understand you correctly you can add a parent pointer in your
Node to acomplish this.

/robo

 

[Mikito Harakiri]

: class Node {
: private Vector children = new Vector(); //
: children.elementAt(i).getType() == Node.class
: private Node parent = null;
: }
: ...
: Now, I wonder how can I reconciliate recursive nature of "server" function
: walkSubTree() with a "client" function nextLeaf() need to receive nodes
: supplied by walkSubTree() in a "discontinous" manner. If after finding a
: leaf could I save the recursion state somehow...

If I understand you correctly you can add a parent pointer in your
Node to acomplish this.

Parent pointer is already there. Your misunderstanding might be due to
accidental comment wrapping to the next line. Here is the Node
definition repeated:

class Node {
private Vector children = new Vector();
private Node parent = null;
static public class Iterator {
public Iterator( Node treeRoot );
public Node nextLeaf();
}
}

On the first invocation The Node.Iterator.nextLeaf() is supposed to
return the first child. Next call to nextLeaf() would return the next
leaf, and null would be returned at the end.

How would I implement this class/method elegantly?

 

[ak]

Here is the Node definition repeated:

class Node {
private Vector children = new Vector();
private Node parent = null;
static public class Iterator {
public Iterator( Node treeRoot );
public Node nextLeaf();
}
}

On the first invocation The Node.Iterator.nextLeaf() is supposed to
return the first child. Next call to nextLeaf() would return the next
leaf, and null would be returned at the end.

How would I implement this class/method elegantly?

class Node {
private Vector children = new Vector();
private Node parent = null;

public Node childAt(int index) {
return (Node)children.elementAt(index);
}

static public class Iterator {
Node root;
int position;

public Iterator( Node treeRoot ) {
this.root = treeRoot;
}
public Node nextLeaf() {
return root.childAt(position++);
}
}
}

 

[Mikito Harakiri]

class Node {
private Vector children = new Vector();
private Node parent = null;

public Node childAt(int index) {
return (Node)children.elementAt(index);
}

static public class Iterator {
Node root;
int position;

public Iterator( Node treeRoot ) {
this.root = treeRoot;
}
public Node nextLeaf() {
return root.childAt(position++);
}
}
}

FYI, leaf in a tree is defined as a node that don't have any children.
Iterating through tree nodes at level 1 is not the same as iterating through
all the leafs.

Here is another view to the problem. Iterating through all the leafs is no
more complex than just iterating through all the nodes filtering out all the
nodes that are not leafs. But how do I flatten a tree into a linear
structure that I can iterate?

 

[Gordon Beaton]

But how do I flatten a tree into a linear structure that I can
iterate?

Simply iterate over the tree in your preferred order, inserting nodes
into a vector or similar linear structure as you go.

/gordon

 

[Mikito Harakiri]

Simply iterate over the tree in your preferred order, inserting nodes
into a vector or similar linear structure as you go.

Is it necessary to maintain a flattened image of tree structure in order to
work with trees? I think no algorithm book prescribes that. But I see that
the question is not for java audience.

 

[Matt Humphrey]

I have a tree modeled like this

class Node {
private Vector children = new Vector(); //
children.elementAt(i).getType() == Node.class
private Node parent = null;
}

I want to write a method nextLeaf(). It's very easy to write a Node's method
that makes recursive depth-first enumeration:

public void walkSubTree() {
for( int i = 0; i < children.size(); i++ )
walkSubTree(children.elementAt(i));
}

Now, I wonder how can I reconciliate recursive nature of "server" function
walkSubTree() with a "client" function nextLeaf() need to receive nodes
supplied by walkSubTree() in a "discontinous" manner. If after finding a
leaf could I save the recursion state somehow...

The subtree walk you describe above does not traverse leaves, but all nodes.
Do you want a real nextLeaf () or a nextNode ()? nextNode cannot be written
without some outside state because for any internal node it cannot
distinguish between next (first child) vs. next as sibling. However,
nextLeaf can. It must be started from the depth-first first leaf of the
root node (firstLeaf ()) and after that each one will find the next leaf.

// Use this on the root node to find the first leaf node.
public Node firstLeaf () {
Node tempNode = this;
while (tempNode.children.size () != 0) {
tempNode = (Node)(tempNode.elementAt (0));
}
return tempNode;
}

// Use this on any leaf node to find the next leaf node
public Node nextLeaf () {
Node tempParent = parent;
while (tempParent != null) {
int nextIndex = tempParent.children.indexOf (this) + 1;
if (nextIndex < tempParent.children.size) {
// I have a sibling (or grand-sibling), so find their first leaf
return (Node)(tempParent.children.elementAt (nextIndex)).firstLeaf
();

} else {
// Oops. Local parent is empty. Shift up to next level
tempParent = tempParent.parent;
}
}

// Oops, ran out of parents. This was the last node
return null;
}

This code has not been tested--it is only to illustrate the algorithm.

Now, if you're looking to get all nodes, that's a bit trickier...

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/

 

[Gordon Beaton]

Is it necessary to maintain a flattened image of tree structure in
order to work with trees? I think no algorithm book prescribes that.
But I see that the question is not for java audience.

No, there's normally no need to maintain a separate flattened copy of
the tree or extra link fields, I was just answering the obvious part
of the previous posters question.

However it can be tricky to implement a mechanism that can start at
any given node N and say what next(N) is. A typical traversal function
is recursive and has only implicit state; it's in the call path used
to reach N.

For example next(N) is the first node in the right child subtree of N.
But if there is no right child, you go to parent(N) and make a choice
that depends on how you got to N in the first place, i.e. the answer
depends on whether N was the right or left child of its parent. If N
was the left child, then next(N) is simply parent(N). But if N was the
right child, you go to parent(parent(N)) and make the same set of
decisions again, etc. So at each node you need to know the path used
to reach N initially, then use that information when you go back up
through the parents to know whether to continue to the right or
upwards.

/gordon

 

[Mikito Harakiri]

The subtree walk you describe above does not traverse leaves, but all nodes.
Do you want a real nextLeaf () or a nextNode ()? nextNode cannot be written
without some outside state because for any internal node it cannot
distinguish between next (first child) vs. next as sibling. However,
nextLeaf can. It must be started from the depth-first first leaf of the
root node (firstLeaf ()) and after that each one will find the next leaf.

Now, this is real attempt to the solution. Thank you, Matt!

// Use this on the root node to find the first leaf node.
public Node firstLeaf () {
Node tempNode = this;
while (tempNode.children.size () != 0) {
tempNode = (Node)(tempNode.elementAt (0));
}
return tempNode;
}

Recursive version:

public Node firstLeaf () {
if( children.size () == 0 )
return this;
return elementAt(0).firstLeaf();
}

// Use this on any leaf node to find the next leaf node
public Node nextLeaf () {
Node tempParent = parent;
while (tempParent != null) {
int nextIndex = tempParent.children.indexOf (this) + 1;
if (nextIndex < tempParent.children.size) {
// I have a sibling (or grand-sibling), so find their first leaf
return (Node)(tempParent.children.elementAt (nextIndex)).firstLeaf
();

} else {
// Oops. Local parent is empty. Shift up to next level
tempParent = tempParent.parent;
}
}

// Oops, ran out of parents. This was the last node
return null;
}

public Node nextLeaf() {
nextIndex = parent.children.indexOf (this) + 1;
if ( nextIndex < parent.children.size )
return parent.children.elementAt(nextIndex).firstChild();
else
return parent.nextLeaf();
}

This still doesn't quite answer my philosophical question, but will keep me
going

 

[Mikito Harakiri]

public Node nextLeaf() {
nextIndex = parent.children.indexOf (this) + 1;
if ( nextIndex < parent.children.size )
return parent.children.elementAt(nextIndex).firstChild();
else
return parent.nextLeaf();
}

Opps. Forgot the case for returning null. If parent is root and there is no
more siblings, end of recursion/iteration.

 

[Mikito Harakiri]

No, there's normally no need to maintain a separate flattened copy of
the tree or extra link fields, I was just answering the obvious part
of the previous posters question.

However it can be tricky to implement a mechanism that can start at
any given node N and say what next(N) is. A typical traversal function
is recursive and has only implicit state; it's in the call path used
to reach N.

For example next(N) is the first node in the right child subtree of N.
But if there is no right child, you go to parent(N) and make a choice
that depends on how you got to N in the first place, i.e. the answer
depends on whether N was the right or left child of its parent. If N
was the left child, then next(N) is simply parent(N). But if N was the
right child, you go to parent(parent(N)) and make the same set of
decisions again, etc. So at each node you need to know the path used
to reach N initially, then use that information when you go back up
through the parents to know whether to continue to the right or
upwards.

That is a nice summary of the problem. I like Matt's idea, however, that
leaf node is a full state description of the traversal, while intermediate
node in the tree is not. Testing it...

 

[Mikito Harakiri]

That is a nice summary of the problem. I like Matt's idea, however, that
leaf node is a full state description of the traversal, while intermediate
node in the tree is not. Testing it...

Worked like charm. The code with typos fixed:

public class Token {
private Vector children = new Vector();
private Token parent = null;

public int childrenCount() {
return children.size();
}
public Token getChild( int i ) {
return (Token)children.elementAt(i);
}
public Token firstLeaf ( Token root ) {
if( childrenCount() == 0 )
return this;
return ((Token)getChild(0)).firstLeaf(root);
}
public Token nextLeaf( Token root ) {
int nextIndex = parent.children.indexOf (this) + 1;
if( parent == root && nextIndex >= parent.childrenCount() )
return null;
if ( nextIndex < parent.childrenCount() )
return parent.getChild(nextIndex).firstLeaf(root);
else
return parent.nextLeaf(root);
}
}

Philosophical part of the discusion is continued at comp.theory...

 

[Matt Humphrey]

leaf.

I'd better clarify here that a naive implementation of the complete node
traversal can be done with an externally explicit stack, but that it isn't
necessary. The iterative algorithm follows:

// The first node is the root node

public Node nextNode () {
if (children.size () > 0) {
return (Node)(children.elementAt (0));
}

Node priorChild = this;
Node tempParent = parent;
while (tempParent != null) {
int nextIndex = tempParent.children.indexOf (priorChild) + 1;
if (nextIndex < tempParent.children.size ()) {
return (Node)(tempParent.children.elementAt (nextIndex));
}

// No more children here--move up one level
priorChild = tempParent;
tempParent = tempParent.parent;
}

// No more nodes
return null;
}

This still doesn't quite answer my philosophical question, but will keep me
going

The short answer is that all recursive algorithms can be converted to
iterative algorithms provided that you (in the worst case) explicity model
the stack. http://www.elis.ugent.be/wog/edegem2003/himpe.pdf For most
practical problems, doing so is more trouble than it's worth.

Cheers,
Matt Humphrey (e-mail address removed) http://www.iviz.com/