GeeksforGeeks:Print Two Balanced Binary Search Trees in sorted form

You are given two balanced binary search trees e.g., AVL or Red Black Tree. Write a function that merges the two given balanced BSTs into a balanced binary search tree. Let there be m elements in first tree and n elements in the other tree. Your merge function should take O(m+n) time.

In the following solutions, it is assumed that sizes of trees are also given as input. If the size is not given, then we can get the size by traversing the tree.

Solution:

 void merge(TreeNode root1, TreeNode root2)  {
  TreeNode node1 = root1, node2 = root2;
  TreeNode lastNode = null;
  TreeNode val1 = root1, val2 = root2;
  Stack<TreeNode> stack1 = new Stack<TreeNode>(), stack2 = new Stack<TreeNode>();
  boolean start1 = true, start2 = true;
  T1:while(true) {
   while(start1) {
    if(node1!=null) {
     stack1.push(node1);
     node1 = node1.left;
    }else {
     if(stack1.isEmpty()) {break T1;}
     node1 = stack1.pop();
     val1 = node1;
     start1 = false;
     node1 = node1.right;
    }
   }
   while(start2) {
    if(node2!=null) {
     stack2.push(node2);
     node2 = node2.left;
    }else {
     if(stack2.isEmpty()) {break T1;}
     node2 = stack2.pop();
     val2 = node2;
     start2 = false;
     node2 = node2.right;
    }
   }
   
   if(val1.val < val2.val) {
    System.out.print(val1.val);
    start1 = true;
    start2 = false;
    lastNode = val2;
    
   }else if(val1.val > val2.val) {
    System.out.print(val2.val);
    start1 = false;
    start2 = true;
    lastNode = val1;
   }
  }
  
  
  System.out.println(lastNode.val);
  inorder(lastNode.right);//the remaining node is a large subtree.
//  if(!stack1.isEmpty()) {
//   node1 = stack1.pop();
//   System.out.println(node1.val);
//  }
//  if(!stack2.isEmpty()) {
//   node2 = stack2.pop();
//   System.out.println(node2.val);
//  }
 }
 
 private void inorder( TreeNode root2) {
  if(root2 == null) return;
  inorder(root2.left);
  System.out.println(root2.val);
  inorder(root2.right);
 }