• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 324
  • Last Modified:

Java Tree Traversal

Hello all,

I have implemented a Depth First Search Tree Traversal in Java, and I now want to take it a step further so you can specify an increment value, which will iteratively deepen the tree. For example, the with an increment of 1, the traversal will only include the root, then the root and its children, then the root and its children and its children etc etc deepening by one every time. The increment value can be updated in a variable as and when needed. My code for Depth First Search is:

    public String DFS(Tree tree) {
        path = "";
        currentNode = null;
        t = null;
        stack = new Stack();
        stack.push(tree); // push root node onto stack
        while (!stack.empty()) { // loop while stack not empty
            currentNode = stack.pop(); // pop off the next node of the stack
            t = (Tree)currentNode; // cast to a tree
            path = path + ((Tree)t).getLabel() + ", "; // add latest to path
            if (t.getRightBranch() != null) stack.push(t.getRightBranch()); // get right node if exists
            if (t.getLeftBranch() != null) stack.push(t.getLeftBranch()); // get left node if exists
        }
        return path;
    }
0
mtcmedia
Asked:
mtcmedia
  • 25
  • 22
  • 3
  • +1
1 Solution
 
petmagdyCommented:
>> Tree tree, is this a Class u developed?
0
 
mtcmediaAuthor Commented:
Yes, sorry. It is a simple class with three methods:

public Tree getLeftBranch()
public Tree getRightBranch()
public String getLabel()
0
 
petmagdyCommented:
0
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
mtcmediaAuthor Commented:
I want to do it using the classes I have created, thats all thats required, just having some problems, I could post what I have so far - but its not right.
0
 
mtcmediaAuthor Commented:
Can anyone help?
0
 
objectsCommented:
Only push children onto stack if the stack contains less nodes than the required depth, something like:

if (stack.size()<=depth)
{
            if (t.getRightBranch() != null) stack.push(t.getRightBranch()); // get right node if exists
            if (t.getLeftBranch() != null) stack.push(t.getLeftBranch()); // get left node if exists
}
0
 
mtcmediaAuthor Commented:
There is no way of checking what depth your at. So it has to be done using the number of stack operations each loop. Ie first loop you get no sets of children, then you get one, then 3 (2+1), then 7 (2+1+4). I think?
0
 
objectsCommented:
> There is no way of checking what depth your at.

The size of the stack is the current depth isn't it?

0
 
mtcmediaAuthor Commented:
No, for example in a tree which looks like:

     1
2        3

With an increment of 1, correct output would be: 1, 1, 2, 3

The stack would look something like:

Visit:
Stack:

Visit:
Stack: 1

Visit: 1
Stack:

Visit: 1
Stack: 2 3

Visit: 1 2
Stack: 3

Visit: 1 2 3
Stack:
0
 
mtcmediaAuthor Commented:
Sorry thats wrong, more like

Visit:
Stack:

Visit:
Stack: 1

Visit: 1
Stack:

Visit: 1 1
Stack: 2 3

Visit: 1 1 2
Stack: 3

Visit: 1 1 2 3
Stack:
0
 
mtcmediaAuthor Commented:
I still think I have missed a step out there, anyway, you know what Im trying to achieve right? :)
0
 
objectsCommented:
before you push the 2 chidren onto the stack, the stack size equals the tree search depth
0
 
mtcmediaAuthor Commented:
So I need to introduce some kind loop into my code above, which loops until the correct depth (stack size) is reached each time :s
0
 
funnyveryfunnyCommented:
try this psuedo code:

level=0; //root
while(stack.hasElements){
   node n = pop();
   if(n!=null) print(n); // or something
   if(n == null) level--; // sift up 1 level, all children of n have been visited
   else if(level<unitIncrement && n!=null){
      push(null); // use _null_ as an indicator of n's children level
      push(RightLeaf);
      push(LeftLeaf);
      level++;
   }
}

By using null as an indicator we can tell whether n's children up to defined unitIncrement have been visited.

So hopefully, I haven't try this out yet, but for a tree like this:

                                        1
                         2                              3
            4                  5              6                7
       8       9       10       11    12   13      14      15

with unitIncrement=2 should give printout like this: 1,2,4,5,3,6,7.
0
 
mtcmediaAuthor Commented:
This is not what Im looking for.

For example in a tree which looks like:
 
         1
    2        3
 4   5    6
 
With an increment of 1, correct output would be: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6
 
The stack would look something like:
 
Visit:
Stack:
 
Visit:
Stack: 1
 
Visit: 1
Stack:
 
Visit: 1
Stack: 1
 
Visit: 1 1
Stack: 2 3
 
Visit: 1 1 2
Stack: 3
 
Visit: 1 1 2 3
Stack:
 
Visit: 1 1 2 3
Stack: 1
 
Visit: 1 1 2 3 1
Stack: 2 3
 
Visit: 1 1 2 3 1 2
Stack: 4 5 3
 
Visit: 1 1 2 3 1 2 4
Stack: 5 3
 
Visit: 1 1 2 3 1 2 4 5
Stack: 3
 
Visit: 1 1 2 3 1 2 4 5 3
Stack: 6
 
Visit: 1 1 2 3 1 2 4 5 3 6
Stack:
0
 
funnyveryfunnyCommented:
I don't fully understand what you're trying to do here.

Give me a few example of different outcomes based on my tree, i.e increment = 1,2,3

Because so far to me it looks like you're using BFS then DFS. A DFS alone will never give the outcome like that.
0
 
mtcmediaAuthor Commented:
It is DFS I am doing here, but the behaviour should go as follows.

To begin with, the tree should be considered to only be the root node, so DFS on the last example would only give : 1. The height of the tree viewed by the DFS is then incremented, above with an increment of 1, so that the tree now is now seen as a root and two children, and so the DFS would show: 1, 2, 3. These two together form the start of the final output shown above:

1, 1, 2, 3

Then then depth is incremented to 3. The root, the roots children, and now their children. Do you see what I mean?
0
 
funnyveryfunnyCommented:
if that the case then you will need a for loop wrapping around my previous code

for(level=0;level<unitIncrement;level++){
  // my previous code.
}

0
 
funnyveryfunnyCommented:
clearer code:

for(level=0;level<unitIncrement;level++){
    int i=0;
    while(stack.hasElements){
       node n = pop();
      if(n!=null) print(n); // or something
      if(n == null) i--; // sift up 1 level, all children of n have been visited
      else if(i<level && n!=null){
      push(null); // use _null_ as an indicator of n's children level
      push(RightLeaf);
      push(LeftLeaf);
      i++;
      }
    }
}
0
 
mtcmediaAuthor Commented:
I will code this now and let you know the result shortly. Thank you!
0
 
funnyveryfunnyCommented:
forgot something:

for(level=0;level<unitIncrement;level++){
    int i=0;
    pop(tree); // given that the stack is empty after each iteration
    while(stack.hasElements){
       node n = pop();
      if(n!=null) print(n); // or something
      if(n == null) i--; // sift up 1 level, all children of n have been visited
      else if(i<level && n!=null){
      push(null); // use _null_ as an indicator of n's children level
      push(RightLeaf);
      push(LeftLeaf);
      i++;
      }
    }
}

:)
0
 
mtcmediaAuthor Commented:
Below is the code I have, I cant see how this will work. The stack is empty to begin with, yet I go to pop off the next element inside the for loop.

   public String DFSdeepening(Tree tree, int increment) {
    int level = 0;
    currentNode = null;
    t = tree;

    for(level=0;level<increment;level++){
    int i=0;
    stack.pop(); // given that the stack is empty after each iteration
    while(!stack.empty()){
       currentNode = stack.pop();
       t = (Tree)currentNode; // cast to a tree
      if(t!=null) System.out.println(t.getLabel()); // or something
      if(t == null) i--; // sift up 1 level, all children of n have been visited
      else if(i<level && t!=null){
      stack.push(null); // use _null_ as an indicator of n's children level
      stack.push(t.getRightBranch());
      stack.push(t.getLeftBranch());
      i++;
      }
    }
}
  return "test";
    }
0
 
funnyveryfunnyCommented:
sorry that should be push() not pop() at begining of for-loop
0
 
mtcmediaAuthor Commented:
I see, I have now run this, and the output is close, but not quite right:

1, 1, 1, 2, 3, 1, 2, 4, 5, 3, 6

This should be:

1, 1, 2, 3, 1, 2, 4, 5, 3, 6
0
 
mtcmediaAuthor Commented:
Sorry no, the output it:

increment = 1
1, 1,

increment = 3
1, 1, 1, 2, 3, 1, 2, 4, 5, 3, 6,

So its quite a bit off
0
 
funnyveryfunnyCommented:
nice to see the idea flourishes...I have a feeling that has to do with if conditions...give me a few minutes to have a look..in the meantime run the loops on paper maybe you'll spot the youknowwhat b4 me :)
0
 
mtcmediaAuthor Commented:
Working through it already on paper as we speak! Not spotted the problem so far, so hopefully you will be able to spot it! Look forward to your reply!
0
 
funnyveryfunnyCommented:
can you give me the code again...
0
 
funnyveryfunnyCommented:
what happen when increment=0?
0
 
mtcmediaAuthor Commented:
 public String DFSdeepening(Tree tree, int increment) {
        path = "";
        int level = 0;
        currentNode = null;
        t = tree;
        stack.push(tree);
        for (level = 0; level < increment; level++) {
            int i = 0;
            stack.push(tree); // given that the stack is empty after each iteration
            while (!stack.empty()) {
                currentNode = stack.pop();
                t = (Tree)currentNode; // cast to a tree
                if (t != null) path = path + ((Tree)t).getLabel() + ", "; // add latest to path // or something
                if (t == null) i--; // sift up 1 level, all children of n have been visited
                else if (i < level && t != null) {
                    stack.push(null); // use _null_ as an indicator of n's children level
                    stack.push(t.getRightBranch());
                    stack.push(t.getLeftBranch());
                    i++;
                }
            }
        }
        return path;
    }
0
 
mtcmediaAuthor Commented:
Output is nothing for 0.
0
 
funnyveryfunnyCommented:
please run this give me all the printout:

  public String DFSdeepening(Tree tree, int increment) {
        path = "";
        currentNode = null;
        for (int level = 0; level < increment; level++) {
            int i = 0;
            stack.push(tree); // given that the stack is empty after each iteration
            while (!stack.empty()) {
                System.out.println("i = "+i);
                currentNode = stack.pop();
                t = (Tree)currentNode; // cast to a tree
                if (t != null) path = path + ((Tree)t).getLabel() + ", "; // add latest to path // or something
                if (t == null) i--; // sift up 1 level, all children of n have been visited
                else if (i < level && t != null) {
                    stack.push(null); // use _null_ as an indicator of n's children level
                    if(t.getRightBranch())
                          stack.push(t.getRightBranch()); //you still need to check for node existen
                    if(t.getLeftBranch())
                          stack.push(t.getLeftBranch());
                    i++;
                }
            }
        }
        return path;
    }

Strange, increment=0 gives nothing!?!
0
 
funnyveryfunnyCommented:
use increment=2
0
 
funnyveryfunnyCommented:
I cant see anything wrong on paper.
0
 
mtcmediaAuthor Commented:
This is the output:

i = 0

i = 0

i = 1

i = 1

i = 1

i = 0

i = 0

i = 1

i = 1

i = 1

i = 0

i = 0

i = 1

i = 1

i = 1
 
1, 1, 2, 3
0
 
funnyveryfunnyCommented:
using increment=2, I expect stack sequence like this:

i=0 ==> stack(null,3,2)     output("1")
i=1 ==> stack(null,3,null,5,4)       output("2")
i=2 ==> stack(null,3,null,5)    output(4)
i=2 ==> stack(null,3,null)    output(5)
i=2 ==> stack(null,3,)
i=1 ==> stack(null,null,6)    output(3)
i=2 ==> stack(null,null)        output(6)
i=1 ==> stack(null)
i=0 ==> stack()

end of while loop. so for(level==increment) gives: 1,2,4,5,3,6
0
 
mtcmediaAuthor Commented:
I have worked some out. Correct output for these values would be:

increment = 1
1, 1, 2, 3, 1, 2, 4, 5, 3, 6,

increment = 3
1, 1, 2, 4, 5, 3, 6,

increment = 5
1, 1, 2, 4, 5, 3, 6,
0
 
funnyveryfunnyCommented:
run with this again please:

public String DFSdeepening(Tree tree, int increment) {
        path = "";
        currentNode = null;
        for (int level = 0; level < increment; level++) {
            System.out.println("level: "+level);
            int i = 0;
            stack.push(tree); // given that the stack is empty after each iteration
            while (!stack.empty()) {
                System.out.println("i = "+i);
                System.out.println("output so far: "+path);
                currentNode = stack.pop();
                t = (Tree)currentNode; // cast to a tree
                if (t != null) path = path + ((Tree)t).getLabel() + ", "; // add latest to path // or something
                if (t == null) i--; // sift up 1 level, all children of n have been visited
                else if (i < level && t != null) {
                    stack.push(null); // use _null_ as an indicator of n's children level
                    if(t.getRightBranch()!=null)
                          stack.push(t.getRightBranch()); //you still need to check for node existen
                    if(t.getLeftBranch()!=null)
                          stack.push(t.getLeftBranch());
                    i++;
                }
            }
        }
        return path;
    }
0
 
mtcmediaAuthor Commented:
increment = 1
1,

increment = 3
1, 1, 2, 3, 1, 2, 4, 5, 3, 6,

increment = 5
1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,

C:\Borland\Together6.2\jdk\bin\javaw -classpath C:\Documents and Settings\Mike Callachan\My Documents\University\CS4104\Practical 2\;C:\Borland\Together6.2\lib\javax.jar; Main


level: 0


i = 0


output so far:


level: 0


i = 0


output so far:


level: 1


i = 0


output so far: 1,


i = 1


output so far: 1, 1,


i = 1


output so far: 1, 1, 2,


i = 1


output so far: 1, 1, 2, 3,


level: 2


i = 0


output so far: 1, 1, 2, 3,


i = 1


output so far: 1, 1, 2, 3, 1,


i = 2


output so far: 1, 1, 2, 3, 1, 2,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6,


level: 0


i = 0


output so far:


level: 1


i = 0


output so far: 1,


i = 1


output so far: 1, 1,


i = 1


output so far: 1, 1, 2,


i = 1


output so far: 1, 1, 2, 3,


level: 2


i = 0


output so far: 1, 1, 2, 3,


i = 1


output so far: 1, 1, 2, 3, 1,


i = 2


output so far: 1, 1, 2, 3, 1, 2,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6,


level: 3


i = 0


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2,


i = 3


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4,


i = 3


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3,


i = 3


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


level: 4


i = 0


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2,


i = 3


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4,


i = 3


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3,


i = 3


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


i = 2


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


i = 1


output so far: 1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,


level: 0


i = 0


output so far:


level: 0


i = 0


output so far:


level: 1


i = 0


output so far: 1,


i = 1


output so far: 1, 1,


i = 1


output so far: 1, 1, 2,


i = 1


output so far: 1, 1, 2, 8,


level: 2


i = 0


output so far: 1, 1, 2, 8,


i = 1


output so far: 1, 1, 2, 8, 1,


i = 2


output so far: 1, 1, 2, 8, 1, 2,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9,


level: 0


i = 0


output so far:


level: 1


i = 0


output so far: 1,


i = 1


output so far: 1, 1,


i = 1


output so far: 1, 1, 2,


i = 1


output so far: 1, 1, 2, 8,


level: 2


i = 0


output so far: 1, 1, 2, 8,


i = 1


output so far: 1, 1, 2, 8, 1,


i = 2


output so far: 1, 1, 2, 8, 1, 2,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9,


level: 3


i = 0


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10,


level: 4


i = 0


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3,


i = 4


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5,


i = 4


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6,


i = 4


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9,


i = 4


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,


i = 4


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,


i = 3


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,


i = 2


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,


i = 1


output so far: 1, 1, 2, 8, 1, 2, 3, 5, 8, 9, 1, 2, 3, 4, 5, 6, 8, 9, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,


level: 0


i = 0


output so far:


level: 0


i = 0


output so far:


level: 1


i = 0


output so far: 1,


i = 1


output so far: 1, 1,


i = 1


output so far: 1, 1, 2,


i = 1


output so far: 1, 1, 2, 114,


level: 2


i = 0


output so far: 1, 1, 2, 114,


i = 1


output so far: 1, 1, 2, 114, 1,


i = 2


output so far: 1, 1, 2, 114, 1, 2,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115,


level: 0


i = 0


output so far:


level: 1


i = 0


output so far: 1,


i = 1


output so far: 1, 1,


i = 1


output so far: 1, 1, 2,


i = 1


output so far: 1, 1, 2, 114,


level: 2


i = 0


output so far: 1, 1, 2, 114,


i = 1


output so far: 1, 1, 2, 114, 1,


i = 2


output so far: 1, 1, 2, 114, 1, 2,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115,


level: 3


i = 0


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116,


level: 4


i = 0


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3,


i = 4


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4,


i = 4


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114, 115,


i = 4


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114, 115, 116,


i = 4


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114, 115, 116, 117,


i = 3


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114, 115, 116, 117,


i = 2


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114, 115, 116, 117,


i = 1


output so far: 1, 1, 2, 114, 1, 2, 3, 113, 114, 115, 1, 2, 3, 4, 113, 114, 115, 116, 1, 2, 3, 4, 5, 113, 114, 115, 116, 117,


0
 
funnyveryfunnyCommented:
the outputs look spot on to me!

given that your tree is limited in size and you're using level=5, I expect repeated patterns.
0
 
funnyveryfunnyCommented:
So method is correct because the i sequence behaves exactly how I expected.
0
 
mtcmediaAuthor Commented:
The output I am expecting is:

increment = 1
1, 1, 2, 3, 1, 2, 4, 5, 3, 6,

increment = 3
1, 1, 2, 4, 5, 3, 6,

increment = 5
1, 1, 2, 4, 5, 3, 6,
0
 
funnyveryfunnyCommented:
why increment=3,5 only produce those outputs?

because from what I understand, I expect those value to produce repeated patterns.

I expect increment=1 gives 1,1,2,3
                          = 2  "      1,1,2,4,5,3,6
                          = 3  "      1,1,2,4,5,3,6,1,2,4,5,3,6
and so on...
0
 
funnyveryfunnyCommented:
another thing level start from 0 so your increment=1 is equivalent to level=2

and correction :

I expect increment= 0 gives 1     <==== the root itself only
                          = 1  "      1,1,2,3
                          = 2  "      1,1,2,3,1,2,4,5,3,6
                          = 3  "      1,1,2,3,1,2,4,5,3,6,1,2,4,5,3,6
0
 
mtcmediaAuthor Commented:
increment = 1
1,

increment = 3
1, 1, 2, 3, 1, 2, 4, 5, 3, 6,

increment = 5
1, 1, 2, 3, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6, 1, 2, 4, 5, 3, 6,

I have double checked, this is the output given.
0
 
funnyveryfunnyCommented:
that's strange, I expect increment = 0 to output: 1,

Are you sure that is the return value of path from your method?

Otherwise, does the method output is how you wanted?
0
 
funnyveryfunnyCommented:
so at the moment method actually returns increment-1, rather than increment! Very strange
0
 
mtcmediaAuthor Commented:
Yup....
0
 
mtcmediaAuthor Commented:
Im still not sure your understanding the problem here.

An increment of 1 will increase the depth of the tree traversed by 1 each time.
0
 
funnyveryfunnyCommented:
let me sumarise what I understood:

>>> you want to print out a tree upto a defined depth level including the print out of all the depth levels up to this defined level using DFS. So a increment=2, expects printout of level 0, 1 and finally level 2.

If my understanding is correct then the method is correct but the only bug is why does it only print out upto increment-1!?!

try with this code:

public String DFSdeepening(Tree tree, int increment) {
        String path = "";
        Tree currentNode = null;
        for (int level = 0; level <= increment; level++) {
            int i = 0;
            stack.push(tree); // given that the stack is empty after each iteration
            while (!stack.empty()) {
                System.out.println("i = "+i);
                currentNode = (Tree) stack.pop();
                if (currentNode != null) path = path + ((Tree)t).getLabel() + ", "; // add latest to path // or something
                if (t == null) i--; // sift up 1 level, all children of n have been visited
                else if (i < level) {
                    stack.push(null); // use _null_ as an indicator of n's children level
                    if(currentNode.getRightBranch()!=null)
                          stack.push(currentNode.getRightBranch()); //you still need to check for node existen
                    if(currentNode.getLeftBranch()!=null)
                          stack.push(currentNode.getLeftBranch());
                    i++;
                }
            }
        }
        return path;
    }

I think the problem here is because I was confused about for-loop, I expected it to execute at least once (regardless of its condition) like do-while loop but it doesn't.

Does this work now?
0
 
mtcmediaAuthor Commented:
>>> you want to print out a tree upto a defined depth level including the print out of all the depth levels up to this defined level using DFS. So a increment=2, expects printout of level 0, 1 and finally level 2.

For an increment=2, it will printout level 0, level 0 level 1, level 0 level 1 level 2
0
 
funnyveryfunnyCommented:
>>>For an increment=2, it will printout level 0, level 0 level 1, level 0 level 1 level 2

lets be clear on which we meant by the term "level", 1) or 2)

1) level means the particular depth of a tree,
    level=0 ==> [1]
    level=1 ==> [(2,3)]
    level=2 ==> [(4,5,6)]
    so increment=2 printout: [1],    [1],[2,3],     [1],[2],[4,5],[3],[6]
          ==> 1,1,2,3,1,2,4,5,3,6

2) level means the whole tree to a particualar depth,
    level=0 ==>  [1],
    level=1 ==>  [(1,2,3)]
    level=2 ==>  [(1,2,4,5,3,6)]
    so printout: [1],     [1],[(1,2,3)],    [1],[(1,2,3)],[(1,2,4,5,3,6)]
        ==> 1,1,1,2,3,1,1,2,3,1,2,4,5,3,6

It's correct for me to say that you're using (1).

You commented that for increment=1, expected

     1, 1, 2, 3, 1, 2, 4, 5, 3, 6,

remember that increment=1 is only upto level 1, method doesn't see further than that. Unless what you want is upto this level including children (meaning upto increment+1) then change the else-if statement to:

       else if(i<=level)

Initially I participated question to help with the concept (how to traverse the tree up a defined level?) and not filling out all the logical steps therefore I expected you to see the bigger picture and work on it.

It is now up to you. :)
0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 25
  • 22
  • 3
  • +1
Tackle projects and never again get stuck behind a technical roadblock.
Join Now