Scan tree structure from bottom up?

Question

If given the following tree structure or one similar to it:

I would want the string ZYXWVUT returned. I know how to do this with a binary tree but not one that can have more than child nodes. Any help would be much appreciated.

Solution 1

This is called a post-order traversal of a tree: you print the content of all subtrees of a tree before printing the content of the node itself.

This can be done recursively, like this (pseudocode):

function post_order(Tree node)
    foreach n in node.children
        post_order(n)
    print(node.text)

Solution 2

If you are maintaining an ArrayList (say node_list) to track the number of nodes branching of from the current tree node, you can traverse the tree from the root till you find a node that has an empty node_list. This way you will be able to identify the leaf nodes of the tree. A recursive approach would work for this case. I haven't tested the code but I believe this should work for what you have asked:

If you are maintaining something similar to the class below to build your tree:

class Node {
     String data;
     ArrayList<Node> node_list;}

The following recursive function might be what you are looking for:

public void traverse_tree(Node n){
    if(n.node_list.isEmpty()){
        System.out.print(n.data);
    }
    else{
        for(Node current_node:n.node_list){
            traverse_tree(current_node);
        }
        System.out.println(n.data);
    }
}

Essentially what you are looking at is the Post-order Depth First traversal of the tree.

Comments

[Ron]

Edited to include a picture, hope you don't mind. As for the OP's concern "I know how to do this with a binary tree but not one that can have more than child nodes": I think tree traversals will work on a tree with any number of child nodes.