How is Backtracking done using recusrion in Binary Tree

Question

I'm trying to insert a Binary Node. My code is convoluted and there's no hope of rescuing it so I plan to rewrite it (basically I didn't account for backtracking and didn't think about the algorithm all that closely).

I'm trying to insert a Binary Node using in order traversal, but I don't understand how I'm supposed to backtrack.

     D
    / \
   B   E 
  / \ / \
 A  C F 

How would I search through the left subtree of root D and then go back and search through the right one? It might be a stupid question, but I'm stumped. The best I can come up with is something like this:

 if (!root.hasLeftChild) {
      root = root.getLeftChild(); 
      recurse(root); 
 } 

But when I reach the bottom, I can't go back up with the root. Also, it doesn't solve the problem where if I reach the bottom left node I have to fill up both children of that node before starting to backtrack.

I think I'm thinking about this the wrong way.

Answer 1

Tree :

     D
    / \
   B   E 
  / \ / \
 A  C F 

For recurse :

Using InOrder Traverse

  if (root == null) 
    return;

      recurse(root.getLeftChild()); 
      int rootData = root.getData();
      recurse(root.getRightChild()); 

Now, how it recurses :

root.getLeftChild() will go on calling the left sub-child recursively unless it hits null node ( so control wont go to recurse(root.getRightChild()); unless null node is hit )

Tree traveled so far :

         D
        / 
       B    
      / 
     A  
    /
  null <-- current Position

So once it reaches node A, A.left == null, so it recurses back to node A (assigning value of node to rootData)

     D
    / 
   B
  / 
 A  <-- current Position

and after this, it goes to next recursive call, recurse(root.getRightChild());

         D
        / 
       B    
      / 
     A  
      \
      null <-- current Position

and now, since left and right of A have been traversed, control will go back to node B (which called b.left = A) and will look for B.right

---

Take this Stack for example, for below tree ( node , value )

     A
    / \
   B   E 
  / \ / \
 C  D F 

Steps :

• A calls its left B, so A pushed in stack
• B calls its left C, so B pushed in stack
• C calls its left null, so C pushed in stack
• Now C has both left and right as null...so this marks the end of recursion for this node, hence its popped out of Stack
• Now, C is traversed completely, so, as B called C , control goes back to B and check which line called this command
• As b.left was executed, it will now go to B.right and push D...... and this goes on , this is called Recursion Stack