CODEWITHSUNDEEP
javaalgorithmtree
user2998228
user2998228

Reputation: 241

Scan tree structure from bottom up?

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

enter image description here

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.

Upvotes: 14

Views: 18039

Answers (3)

Rohit Jose
Rohit Jose

Reputation: 188

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.

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726509

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.

Post-order traversal

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

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

Upvotes: 21

BevynQ
BevynQ

Reputation: 8259

something like this should do it

public void traverse(){
    for(Child child : this.children){
        child.traverse();
    }
    System.out.print(this.value);
}

Upvotes: 0

Related Questions