This week's book giveaways are in the Java EE and JavaScript forums.
We're giving away four copies each of The Java EE 7 Tutorial Volume 1 or Volume 2(winners choice) and jQuery UI in Action and have the authors on-line!
See this thread and this one for details.
The moose likes Java in General and the fly likes B-Tree- method inorder(TreeNode<E> root) Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "B-Tree- method inorder(TreeNode<E> root)" Watch "B-Tree- method inorder(TreeNode<E> root)" New topic
Author

B-Tree- method inorder(TreeNode<E> root)

Ana Vukovic
Greenhorn

Joined: Jan 12, 2013
Posts: 3
I understand recursive methods, but not this one:

protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}



I will be vary greatfull if someone explain me step by step how this method print nodes by order

Seetharaman Venkatasamy
Ranch Hand

Joined: Jan 28, 2008
Posts: 5575

welcome to CodeRanch Ana

Hmm... can you do the same functionality without recursion ? earlier jdk cost recursion since recursion cost on method calls ...

IMO, recursion may reduce number of line ..that's all nothing afterwards...
Stephan van Hulst
Bartender

Joined: Sep 20, 2010
Posts: 3615
    
  14

The code is actually really simple. First it prints all nodes on the left of the root inorder, then it prints the root, and then it prints all nodes on the right of the root inorder.

Imagine putting your hand on the top of the tree, and squashing it flat. The line of elements that you get is the resulting String.
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38467
    
  23
Welcome again
There is a subtle difference between that method and what I have seen. What I have seen isSubtle difference, but important. The first method you wrote was a static method of the class; what I have written is an instance method of the node object. If value cannot be printed with the %s tag, you would have to change the printf call slightly.
Ana Vukovic
Greenhorn

Joined: Jan 12, 2013
Posts: 3
Ana Vukovic wrote:I understand recursive methods, but not this one:

protected void inorder(TreeNode<E> root) {
if (root == null) return;
inorder(root.left);
System.out.print(root.element + " ");
inorder(root.right);
}



I will be vary greatfull if someone explain me step by step how this method print nodes by order



First, thanks guys for helping me!!!

Second...

This method first print last node (leaf) in the left subtree, then goes back (to parent node) print that node, and if that node has right child print that and than goes back to parent node, and goes back one more and print that node, and if that node has right child print it........and so on to the root, print root and goes to the right subtree , goes to the last left node (leaf) print........

That is how this method should work.

But I don't understand how. First i don't now how to put picture of some tree.....MY ENGLISH IS NOT GOOD, (I appologise)so I maybe don't explain it vary well......

If we look this method...firs we pass root to this method, if the root isn't null root become his child and we pass that node to the method inorder(root.left) and start from beginning, if root.left isn't null root.left become his child and so on until we go to the last element which is null and start over, if node is null (which is true) return; THAN WHAT....when we are going to print this node?


Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38467
    
  23
Go to node 1 which is not null. Its left branch is not null, so go to that = 2.
Its left node is no null so go to that = 3. 3 has two nulls for left and right, so print 3.value, then 2.value, then try 2.right = 4.
4 has two nulls, so print 4 and back to 2 and back to 1.
1’s left branch is finished with, so print 1.value and try 1.right = 5.
5 has a null on the left, so print 5.value and try 5.right = 6.
6 has a null on the left, so print 6.value and try 6.right = 7.
7 has two nulls, so print 7.value and return control via 6-5-1.
Ana Vukovic
Greenhorn

Joined: Jan 12, 2013
Posts: 3
Campbell Ritchie wrote:Go to node 1 which is not null. Its left branch is not null, so go to that = 2.
Its left node is no null so go to that = 3. 3 has two nulls for left and right, so print 3.value, then 2.value, then try 2.right = 4.
4 has two nulls, so print 4 and back to 2 and back to 1.
1’s left branch is finished with, so print 1.value and try 1.right = 5.
5 has a null on the left, so print 5.value and try 5.right = 6.
6 has a null on the left, so print 6.value and try 6.right = 7.
7 has two nulls, so print 7.value and return control via 6-5-1.


So, when it comes to 3.left which is null,key word return means to go back , skip inorder(root.left); print, and check right node?
I thing I got it!!! Thanks
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 38467
    
  23
I would not use the keyword return in that context myself, but, yes, you have got it
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: B-Tree- method inorder(TreeNode<E> root)