java - How is Backtracking done using recusrion in Binary Tree -

i'm trying insert binary node. code convoluted , there's no hope of rescuing plan rewrite (basically didn't account backtracking , didn't think algorithm closely).

i'm trying insert binary node using in order traversal, don't understand how i'm supposed backtrack.

     d     / \    b   e    / \ / \   c f  

how search through left subtree of root d , go , search through right one? might stupid question, i'm stumped. best can come this:

 if (!root.hasleftchild) {       root = root.getleftchild();        recurse(root);   }  

but when reach bottom, can't go root. also, doesn't solve problem if reach bottom left node have fill both children of node before starting backtrack.

i think i'm thinking wrong way.

tree :

     d     / \    b   e    / \ / \   c f  

for recurse :

using inorder traverse

  if (root == null)      return;        recurse(root.getleftchild());        int rootdata = root.getdata();       recurse(root.getrightchild());  

now, how recurses :

root.getleftchild() go on calling left sub-child recursively unless hits null node ( so control wont go recurse(root.getrightchild()); unless null node hit )

tree traveled far :

         d         /         b           /             /   null <-- current position 

so once reaches node a, a.left == null, recurses node a (assigning value of node rootdata)

     d     /     b   /    <-- current position 

and after this, goes next recursive call, recurse(root.getrightchild());

         d         /         b           /               \       null <-- current position 

and now, since left , right of a have been traversed, control go node b (which called b.left = a) , b.right

---

take stack example, below tree ( node , value )

         / \    b   e    / \ / \  c  d f  

steps :

• a calls left b, pushed in stack
• b calls left c, b pushed in stack
• c calls left null, c pushed in stack
• now c has both left , right null...so marks end of recursion node, hence popped out of stack
• now, c traversed completely, so, b called c , control goes b , check line called command
• as b.left executed, go b.right , push d...... and goes on , called recursion stack