CODEWITHSUNDEEP
algorithmrecursiontree
EricCui
EricCui

Reputation: 75

Non-recursive n-ray tree traversal

Given class definition as:

class Node {
    public Double value;
    public List<Node> children;
}

Translate the following program into non-recursive:

public static void process(Node node) { 
    for (int i = 0; i < node.children.size(); i++) {
        Node child = node.children.get(i);
        if (child.value < node.value) {
            process(child);
        }
    }
    System.out.println(node.value);
    for (int i = 0; i < node.children.size(); i++) {
        Node child = node.children.get(i);
        if (child.value >= node.value) {
            process(child);
        }
    }
}

The common tree traversal algorithm seems to be suitable here, since the stack pop needs to check the condition.

Really cannot think of a solution.

I get the following output when using the sample tree as shown in the code:

5.7 6.0 1.0 12.0 13.0 5.0 8.0 7.0 10.0 9.0 5.5 15.0 11.0 14.0

public class Node {
public Double value;
public List<Node> children;
public Node(Double value) {
    this.value = value;
    this.children = new ArrayList<Node>();
}
public void addChild(Node node) {
    children.add(node);
}
public static Node createSample() {
    Node node = new Node(10.0);
    Node node1 = new Node(15.0);
    Node node2 = new Node(6.0);
    Node node3 = new Node(11.0);
    Node node4 = new Node(14.0);
    Node node5 = new Node(5.0);
    node.addChild(node1);
    node.addChild(node2);
    node.addChild(node3);
    node.addChild(node4);
    Node node51 = new Node(8.0);
    Node node52 = new Node(7.0);
    node5.addChild(node51);
    node5.addChild(node52);
    node.addChild(node5);
    Node node11 = new Node(9.0);
    Node node12 = new Node(5.5);
    node1.addChild(node11);
    node1.addChild(node12);
    Node node21 = new Node(5.7);
    Node node22 = new Node(12.0);
    node2.addChild(node21);
    node2.addChild(node22);
    Node node31 = new Node(13.0);
    Node node32 = new Node(1.0);
    node22.addChild(node31);
    node22.addChild(node32);
    return node;
}

}

Upvotes: 0

Views: 1611

Answers (2)

ilim
ilim

Reputation: 4547

One method is to manually implement what recursive process does, utilizing the same mechanism used by memory when recursive calls are made. Namely, recursive calls are made by utilizing the stack structure of the memory. A non-recursive tree traversal can also be simulated by using a stack similar to that used by the memory. Then, the traversal will consist of a loop where you keep pushing children onto the stack, and visit(pop) the first children. The loop will terminate when there are no more nodes in the stack. This is the same as recursive traversal you are making, also known as post-order tree traversal. One may even consider this approach as depth-first search, if instead of trees you were handling graphs.

However one thing you fail to verbally mention in your question is the need to process the children in the order of magnitude of their values. For that, you would just need to fiddle with the order in which you put the elements inside the stack. Remember, since stack is a LIFO(last-in-first-out) data structure, you would need to put the elements with values higher than the parent node before the ones with smaller values.

Below is a sample, and not very efficient implementation of the solution I described above. You may observe this solution at work here, producing the same output you provided in your question.

class StackNode {
    public Node node;
    public boolean largerChildrenPushed;
    public StackNode(Node n) {
        this.node = n;
        this.largerChildrenPushed = false;
    }
}
public static void process(Node node) {
    Stack st = new Stack();
    st.push(new StackNode(node));
    while(!st.empty()) {
        StackNode stParent = (StackNode)st.pop();
        Node parent = stParent.node;
        if(!stParent.largerChildrenPushed) {
            for (int i = parent.children.size() - 1; i >= 0; i--) {
                Node child = parent.children.get(i);
                if (child.value >= parent.value) {
                    st.push(new StackNode(child));
                }
            }
            st.push(stParent);
            stParent.largerChildrenPushed = true;
            for (int i = parent.children.size() - 1; i >= 0; i--) {
                Node child = parent.children.get(i);
                if (child.value < parent.value) {
                    st.push(new StackNode(child));
                }
            }
        }
        else {
            System.out.println(parent.value);
        }
    }
}

Upvotes: 1

Sahir
Sahir

Reputation: 329

I can not provide you a solution but a hint to move forth to your logic. Think of the data structure that uses recursion when it's executing in the memory. Use that data structure to push and pop things up and traverse until your data structure has nothing else to traverse.

And, first figure out which type of tree traversal is it? Break your logic to small chunks and go forth dealing it with them one by one in your non-recursive/iterative code.

Upvotes: 1

Related Questions