• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

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

 
Ana Vukovic
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 5575
Eclipse IDE Java Windows XP
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 5590
55
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 48652
56
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would not use the keyword return in that context myself, but, yes, you have got it
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic