1

I was trying to convert recursive program to non recursive program. Purpose of the program is traversal of the data structure.

Please find below data structure

class Node {
}

class LeafNode extends Node {
    private int leafNodeValue;

    public LeafNode (int leafNodeValue) {
        this.leafNodeValue= leafNodeValue;
    }

   public int getLeafNodeValue() {
      return leafNodeValue;
   }
   public void setLeafNodeValue(int leafNodeValue ) {
     this.leafNodeValue = leafNodeValue;
   }
}

class NonLeafNode extends Node {
    private List<Node> nodeList = new ArrayList<>();

    public List<Node> getNodeList() {
       return nodeList ;
    }
    public void setNodeList(List<Node> nodeList) {
       this.nodeList = nodeList;
    }
}

Here is my recursive node traversal class that I'm having trouble rewriting non-recursively.

Recursive Traversal Class

public class RecursiveTraversal {
    public static void main (String[] args ) {
        NonLeafNode node1 = new NonLeafNode();

        NonLeafNode node2 = new NonLeafNode();
        node2.getNodeList().add(new LeafNode(1));

        NonLeafNode node3 = new NonLeafNode();
        node3.getNodeList().add(new LeafNode(2));

        node2.getNodeList().add(node3);

        NonLeafNode node4 = new NonLeafNode();
        node4.getNodeList().add(new LeafNode(3));

        node1.getNodeList().add(node2);
        node1.getNodeList().add(node4);
        node1.getNodeList().add(new LeafNode(4));

        for (Node nodeItem : node1.getNodeList())
            traverse(nodeItem);
    }

    public static void traverse (Node node) {
        if (node instanceof LeafNode)
            System.out.println(" Leaf Node " + ((LeafNode) node).getLeafNodeValue());
        else if (node instanceof NonLeafNode)
            for (Node nodeItem: ((NonLeafNode) node).getNodeList())
                traverse(nodeItem);
    }
}

Output of the program should be 1,2,3,4.

Can someone please help me to write iterative version of above program?

Mahesh
  • 312
  • 1
  • 12
  • `class Node() { ... }` is this correct in java? – Cid Sep 25 '18 at 06:49
  • yes my top level class is RecursiveTraversal all other classes are contained in the same file, I am able to execute the program get output, might have made some error while typing in browser but mostly it should run with minor changes. – Mahesh Sep 25 '18 at 06:50
  • You have a lots of compile error. Fix and wait for help. No one dont have to fix your fault. Your question is about logic on iterative , but code is not working. – drowny Sep 25 '18 at 06:51
  • 1
    Step 1: Recognize that your recursive method is a [Depth-First Search](https://en.wikipedia.org/wiki/Depth-first_search). --- Step 2: Do a web search for how to do that without recursion: [`non-recursive depth first search`](https://www.google.com/search?q=non-recursive+depth+first+search) – Andreas Sep 25 '18 at 06:53
  • removed all the compilation error please check now – Mahesh Sep 25 '18 at 07:29
  • Andreas, depth first search traversal work for me thanks – Mahesh Sep 25 '18 at 08:27

1 Answers1

0

To make it iterative, just use a while loop or a for loop.

So something like:

while(getLeafNode() != null) {
  // etc
}

Also:

prvate int leafNodeValue;

Probably should be private not prvate?

Rick
  • 576
  • 3
  • 12