title: How to print integers in ascending order from a balanced binary search tree?
body: <p>This a program creates balanced binary search tree from an array integer and later on, prints the value in-order ( X.left, X, X.right). Any suggestion for improving the program appreciated. </p>
  
  <p>It would be good to note, there are several other ways for traversing a BST. Such as -
  Pre-order : X, X.left, X.right
  Post-order : X.left, X.right, X </p>
  
  <p>Note # I eventually solved the issue with some help from the user of this program. It needed to change some conditions inside the <em>createMinimalBST</em> method. </p>
  
  <pre><code>// we need to stop recursion there as one element exist
  if (start == mid-1) {
  
  }
  
  // we need to stop recursion there as one element exist
  if (end == mid+1) {
  
  }
  </code></pre>
  
  <p>THANK YOU. </p>
  
  <pre><code>// import java.util.Arrays;
  // import java.util.LinkedList;
  import java.util.*; 
  
  class Node {
  
      int key;
  
      Node leftChild;
      Node rightChild;
  
      Node(int key) {
          this.key = key;
      }
  
      Node() {
          // null constructor 
      }
  
      public String toString() {
          return "\n"+key+" ";
      }
  }
  
  
  public class BinaryTree {
  
      Node root;
  
      static int TWO_NODES_FOUND = 2;
      static int ONE_NODE_FOUND = 1;
      static int NO_NODES_FOUND = 0;
  
      BinaryTree (){
          root = null;
      }
  
      public void addNode(int key) {
  
          Node newNode = new Node(key);
  
          // If there is no root this becomes root
          if (root == null) {
              root = newNode;
          } 
  
          else {
  
              // Set root as the Node we will start
              // with as we traverse the tree
  
              Node focusNode = root;
              Node parent;
  
              while (true) {
  
                  parent = focusNode;
  
                  if (key &lt; focusNode.key) {
  
                      focusNode = focusNode.leftChild;
  
                      if (focusNode == null) {
  
                          parent.leftChild = newNode;
                          return; // All Done
                      }
                  } // end of if 
  
                  else { 
  
                      focusNode = focusNode.rightChild;
  
                      if (focusNode == null) {
  
                          parent.rightChild = newNode;
                          return; 
                      }
                  }
              }
          }
      }
  
      // get the height of binary tree 
      public int height(Node root) {
  
          if (root == null)
              return -1;
  
          Node focusNode = root; 
          int leftHeight = focusNode.leftChild != null ? height( focusNode.leftChild) : 0;
          int rightHeight = focusNode.rightChild != null ? height( focusNode.rightChild) : 0;
          return 1 + Math.max(leftHeight, rightHeight);
      }
  
      // METHODS FOR THE TREE TRAVERSAL
  
      // inOrderTraverseTree : i) X.left ii) X iii) X.right
      public void inOrderTraverseTree(Node focusNode) {
  
          if (focusNode != null) {
  
              inOrderTraverseTree(focusNode.leftChild);
              // System.out.println(focusNode);
              System.out.print( focusNode );
              inOrderTraverseTree(focusNode.rightChild);
          }
          // System.out.println();
      }
  
      // preOrderTraverseTree : i) X ii) X.left iii) X.right
      public void preorderTraverseTree(Node focusNode) {
  
          if (focusNode != null) {
  
              System.out.println(focusNode);
              preorderTraverseTree(focusNode.leftChild);
              preorderTraverseTree(focusNode.rightChild);
  
          }
      }
  
      // postOrderTraverseTree : i) X.left ii) X.right iii) X
      public void postOrderTraverseTree(Node focusNode) {
  
          if (focusNode != null) {
  
              preorderTraverseTree(focusNode.leftChild);
              preorderTraverseTree(focusNode.rightChild);
              System.out.println(focusNode);
  
          }
      }
  
      // get certain node from it's key
      public Node findNode(int key) {
  
          Node focusNode = root;
  
          while (focusNode.key != key) {
  
              if (key &lt; focusNode.key) {
  
                  focusNode = focusNode.leftChild;
  
              } else {
  
                  focusNode = focusNode.rightChild;
              }
  
              if (focusNode == null)
                  return null;
          }
          return focusNode;
  
      }
  
  
      public boolean remove(int key) {
  
          Node focusNode = root;
          Node parent = root;
          boolean isItALeftChild = true;
  
  
          // we will remove the focusNode 
          while (focusNode.key != key) {
  
              parent = focusNode;
  
              if (key &lt; focusNode.key) {
  
                  isItALeftChild = true;
                  focusNode = focusNode.leftChild;
              } 
  
              else {
  
                  isItALeftChild = false;
                  focusNode = focusNode.rightChild;
              }
  
              if (focusNode == null)
                  return false;
          }
  
          // no child 
          if (focusNode.leftChild == null &amp;&amp; focusNode.rightChild == null) {
  
              if (focusNode == root)
                  root = null;
  
              else if (isItALeftChild)
                  parent.leftChild = null;
  
              else
                  parent.rightChild = null;
          }
  
          // one child ( left child )
          else if (focusNode.rightChild == null) {
  
              if (focusNode == root)
                  root = focusNode.leftChild;
  
              else if (isItALeftChild)
                  parent.leftChild = focusNode.leftChild;
  
              else
                  parent.rightChild = focusNode.leftChild;
          }
  
  
          else if (focusNode.leftChild == null) {
  
              if (focusNode == root)
                  root = focusNode.rightChild;
  
              else if (isItALeftChild)
                  parent.leftChild = focusNode.rightChild;
  
              else
                  parent.rightChild = focusNode.rightChild;
  
          }
  
          // two children exits 
          else {
  
              // replacement is the smallest node in the right subtree 
              // we neeed to delete the focusNode 
              Node replacement = getReplacementNode(focusNode);
  
              if (focusNode == root)
                  root = replacement;
  
              else if (isItALeftChild)
                  parent.leftChild = replacement;
  
              else
                  parent.rightChild = replacement;
  
              replacement.leftChild = focusNode.leftChild;
          }
  
          return true;
      }
  
  
  
      public Node getReplacementNode(Node replacedNode) {
  
          Node replacementParent = replacedNode;
          Node replacement = replacedNode;
          Node focusNode = replacedNode.rightChild;
  
          // find the smallest node of the right subtree of the node to be deleted 
          while (focusNode != null) {
  
              replacementParent = replacement;
              replacement = focusNode;
              focusNode = focusNode.leftChild;
          }
  
          // exit when the focusNode is null
          // the replacement is the smallest of the right subtree
  
          if (replacement != replacedNode.rightChild) {
  
              replacementParent.leftChild = replacement.rightChild;
              replacement.rightChild = replacedNode.rightChild;
          }
  
          return replacement;
      }
  
  
      private  void createMinimalBST(int arr[], int start, int end, Node newNode){
  
          if ( end &lt;= start ) return;
  
          int mid = (start + end) / 2;
          newNode.key = arr[mid];
  
          // System.out.println("new node = "+ newNode );
  
           if (start &lt;= mid-1) {
              if ( start &lt; mid-1){
                  newNode.leftChild = new Node();
                  createMinimalBST( arr, start, mid - 1, newNode.leftChild );
              }
              else {
                  newNode.leftChild = new Node();
                  newNode.leftChild.key = arr[start];
              }
          }
  
          if ( mid+1 &lt;= end ) {
  
              if ( mid+1 &lt; end){
  
                  newNode.rightChild = new Node();
                  createMinimalBST(arr, mid + 1, end, newNode.rightChild); 
              }
  
              else {
                  newNode.rightChild = new Node();
                  newNode.rightChild.key = arr[end];
              }
          }
  
          // System.out.println("left child = "+ newNode.leftChild +" "+ " right child = "+ newNode.rightChild);        
  
      } 
  
      public static int getHeight(Node root) {
          if (root == null) {
              return 0;
          }
          return Math.max(getHeight(root.leftChild), getHeight(root.rightChild)) + 1;
      }
  
      public static boolean isBalanced( Node root) {
          if (root == null) {
              return true;
          }
          int heightDiff = getHeight(root.leftChild) - getHeight(root.rightChild);
  
          if (Math.abs(heightDiff) &gt; 1) {
              return false;
          }
          else {
              return isBalanced(root.leftChild ) &amp;&amp; isBalanced(root.rightChild );
          }       
      }
  
      public void createMinimalBST(int array[]) {
  
          // Node n = new Node();
          Arrays.sort(array);
          root = new Node();
          createMinimalBST(array, 0, array.length - 1, root);
      }
  
      // create linked list of the same level of the tree
      public static ArrayList&lt;LinkedList&lt;Node&gt;&gt; createLevelLinkedList( Node root) {
  
          ArrayList&lt;LinkedList&lt;Node&gt;&gt; result = new ArrayList&lt;LinkedList&lt;Node&gt;&gt;();
  
          /* "Visit" the root */
          LinkedList&lt;Node&gt; current = new LinkedList&lt;Node&gt;();
  
          if ( root != null) {
              current.add(root);
          }
  
          while ( current.size() &gt; 0) {
  
              result.add(current); // Add previous level
              LinkedList&lt;Node&gt; parents = current; // Go to next level
  
              current = new LinkedList&lt;Node&gt;(); 
  
              for ( Node parent : parents) {
  
                  /* Visit the children */
                  if (parent.leftChild != null) {
                      current.add(parent.leftChild);
                  }
  
                  if (parent.rightChild != null) {
                      current.add(parent.rightChild );
                  }
              }   
  
          }
  
          return result;
      }
  
      // print values in the same level of the tree gradually 
      public static void printResult(ArrayList&lt;LinkedList&lt;Node&gt;&gt; result){
  
          int depth = 0;      
  
          for(LinkedList&lt;Node&gt; entry : result) {
  
              Iterator&lt;Node&gt; i = entry.listIterator();
              System.out.print("Link list at depth " + depth + ":");
  
              while(i.hasNext()){
                  System.out.print(" " + ((Node)i.next()).key );
              }
  
              System.out.println();
              depth++;    
          }       
      }
  
  
      // using a key, check whether the node is inside of the BST or not 
      public boolean isBST (int n){
  
          if ( n == root.key ){
              return true;
          }
  
          else {
  
              Node focusNode = root;
              Node parent; 
  
              while( focusNode != null){
  
                  parent = focusNode;
  
                  if (focusNode != null){
  
                      if (n &lt; focusNode.key){
  
                          focusNode = focusNode.leftChild;
                      }
  
                      else {
  
                          focusNode = focusNode.rightChild;
  
                      }
                  }
  
                  if ( focusNode != null &amp;&amp;   n == focusNode.key ){
                      return true;
  
                  }
              }
          }
          return false;
      }
  
  
      // 
      public Node getNode (int n){
  
          if ( n == root.key ){
              return root;
          }
  
          else {
  
              Node focusNode = root;
              Node parent; 
  
              while( focusNode != null){
  
                  parent = focusNode;
  
                  if (focusNode != null){
  
                      if (n &lt; focusNode.key){
  
                          focusNode = focusNode.leftChild;
                      }
  
                      else {
  
                          focusNode = focusNode.rightChild;
  
                      }
                  }
  
                  if ( focusNode != null &amp;&amp;   n == focusNode.key ){
                      return focusNode;
  
                  }
              }
          }
          return null;
      }
  
  
      // get the parent of using the key of certain node 
      public Node getParent (int n){
  
          if ( !isBST (n)){
              return null;
          }
  
          if ( n == root.key ){
              return null;
          }
  
          else {
  
              Node focusNode = root;
              Node parent; 
  
              while( focusNode != null){
  
                  parent = focusNode;
  
                  if (focusNode != null){
  
                      if (n &lt; focusNode.key){
  
                          focusNode = focusNode.leftChild;
                      }
  
                      else {
  
                          focusNode = focusNode.rightChild;
  
                      }
                  }
  
                  if ( focusNode != null &amp;&amp; n == focusNode.key ){
                      return parent;
                  }
              }
          }
  
          return null;
      }
  
  
      /* get in-order successive node of the certain node */
      public  Node inorderSucc( Node n) { 
  
          if (n == null) return null;
  
          // Found right children -&gt; return left most node of right subtree
          if ( getParent(n.key)    == null || n.rightChild != null) { 
              return leftMostChild( n.rightChild ); 
          } 
  
          else { 
  
              Node q = n;
              Node x = getParent(q.key);
  
              // Go up until we’re on left instead of right
              while (x != null &amp;&amp; x.leftChild != q) {
                  q = x;
                  x = getParent(x.key);
              }
              return x;
          }  
      } 
  
      /* get the left most/ smallest node of the sub tree of the certain node */
      public  Node leftMostChild( Node n) {
  
          if (n == null) {
              return null;
          }
  
          while (n.leftChild != null) {
              n = n.leftChild; 
          }
          return n; 
      }
  
  
      // SECOOND SOLUTION TO FIND OUT THE COMMON ANCESTOR OF TWO NODES 
  
      public static boolean covers2( Node root, Node p) { 
  
          if (root == null) return false;
          if (root == p) return true;
          return covers2(root.leftChild , p) || covers2(root.rightChild , p); 
      }
  
      public static Node commonAncestorHelper( Node root, Node p, Node q) {
          if (root == null) {
              return null;
          }
          boolean is_p_on_left = covers2(root.leftChild , p);
          boolean is_q_on_left = covers2(root.leftChild , q);
          if (is_p_on_left != is_q_on_left) { // Nodes are on different side
              return root;
          }
  
          // nodes are the same sides
          Node child_side = is_p_on_left ? root.leftChild : root.rightChild;
          return commonAncestorHelper(child_side, p, q);
  
      }
  
      public static Node commonAncestor2( Node root, Node p, Node q) {
  
          if (!covers2(root, p) || !covers2(root, q)) { // Error check - one node is not in tree
              return null;
          }
          return commonAncestorHelper(root, p, q);
      }
      // END OF THE SECOND SOLUTION 
  
  
      // FIRST SOLUTION TO FIND OUT THE COMMON ANCESTOR OF TWO NODES
        // Checks how many “special” nodes are located under this root
      public static int covers( Node root, Node p, Node q) {
          int ret = NO_NODES_FOUND;
          if (root == null) return ret;
          if (root == p || root == q) 
              ret += 1;
          ret += covers(root.leftChild , p, q);
          if(ret == TWO_NODES_FOUND) // Found p and q 
              return ret;
          return ret + covers(root.rightChild , p, q);
      }
  
  
      public static Node commonAncestor( Node root, Node p, Node q) {
  
          if (q == p &amp;&amp; (root.leftChild == q || root.rightChild == q)) 
              return root;
  
          int nodesFromLeft = covers(root.leftChild, p, q); // Check left side
  
          if ( nodesFromLeft == TWO_NODES_FOUND ) {
  
              if(root.leftChild == p || root.leftChild == q) 
                  return root.leftChild;
              else return commonAncestor(root.leftChild , p, q);
          } 
  
          else if (nodesFromLeft == ONE_NODE_FOUND) {
  
              if (root == p) return p;
              else if (root == q) return q;
          }
  
          int nodesFromRight = covers(root.rightChild, p, q); // Check right side
  
          if(nodesFromRight == TWO_NODES_FOUND) {
  
              if(root.rightChild == p || root.rightChild == q) 
                  return root.rightChild;
  
              else return commonAncestor(root.rightChild , p, q);
          } 
  
          else if (nodesFromRight == ONE_NODE_FOUND) {
              if (root == p) return p;
              else if (root == q) return q;
          }
  
          if (nodesFromLeft == ONE_NODE_FOUND &amp;&amp; 
              nodesFromRight == ONE_NODE_FOUND) return root;
          else return null;
      }
      // END OF THE FIRST SOLUTION 
  
  
      // METHODS FOR SUBTREE CHECK 
      // Check if T2 is subtree of T1     
      public static boolean containsTree( Node t1, Node t2) {
          if (t2 == null)
              return true; // The empty tree is a subtree of every tree.
          else
              return subTree(t1, t2);
      }
  
  
      /* Checks if the binary tree rooted at r1 contains the binary tree 
       * rooted at r2 as a subtree somewhere within it.
       */
  
      public static boolean subTree( Node r1, Node r2) {
  
          if (r1 == null)
              return false; // big tree empty &amp; subtree still not found.
          if (r1.key == r2.key) {
              if (matchTree(r1,r2)) return true;
          }
          return (subTree(r1.leftChild , r2) || subTree(r1.rightChild , r2)); 
      }
  
      /* 
        Checks if the binary tree rooted at r1 contains the 
        binary tree rooted at r2 as a subtree starting at r1.
       */
  
      public static boolean matchTree( Node r1, Node r2) {
  
          if (r2 == null &amp;&amp; r1 == null) 
              return true; // nothing left in the subtree
          if (r1 == null || r2 == null) 
              return false; //  big tree empty &amp; subtree still not found
          if (r1.key != r2.key) 
              return false;  // data doesn’t match
          return (matchTree(r1.leftChild, r2.leftChild) &amp;&amp; 
                  matchTree(r1.rightChild , r2.rightChild ));
      }
      // END OF SUBTREE CHECK 
  
  
          /* Creates tree by mapping the array left to right, top to bottom. */
      public  Node createTreeFromArray(int[] array) {
  
          if (array.length &gt; 0) {
  
              root = new Node(array[0]);
              java.util.Queue&lt;Node&gt; queue = new java.util.LinkedList&lt;Node&gt;();
              queue.add(root);
              boolean done = false;
              int i = 1;
  
              while (!done) {
  
                  Node r = (Node) queue.element();
  
                  if (r.leftChild == null) {
  
                      r.leftChild = new Node(array[i]);
                      i++;
                      queue.add(r.leftChild);
                  } 
  
                  else if (r.rightChild == null) {
                      r.rightChild = new Node(array[i]);
                      i++;
                      queue.add(r.rightChild );
                  } 
  
                  else {
                      queue.remove();
                  }
  
                  if (i == array.length)
                      done = true;
              }
  
              return root;
          } 
  
          else {
              return null;
          }
      }
  
  
      // ALGORITHM TO FIND ALL THE PATHS TO CERTAIN SUM VALUE 
  
      public static void findSum( Node node, int sum, int[] path, int level) {
  
          if (node == null) {
              return;
          }
  
          /* Insert current node into path */
          path[level] = node.key; 
  
          int t = 0;
          for (int i = level; i &gt;= 0; i--){
  
              t += path[i];
              if (t == sum) {
                  print(path, i, level);
              }
          }
  
          findSum( node.leftChild, sum, path, level + 1);
          findSum( node.rightChild , sum, path, level + 1);
  
          /* Remove current node from path. Not strictly necessary, since we would
           * ignore this value, but it's good practice.
           */
          path[level] = Integer.MIN_VALUE; 
      }
  
      public static int depth( Node node) {
  
          if (node == null) {
              return 0;
          } 
  
          else {
              return 1 + Math.max(depth(node.leftChild), depth(node.rightChild));
          }
      }
  
      public static void findSum( Node node, int sum) {
  
          int depth = depth(node);
          int[] path = new int[depth];
          findSum(node, sum, path, 0);
      }
  
      private static void print(int[] path, int start, int end) {
          for (int i = start; i &lt;= end; i++) {
              System.out.print(path[i] + " ");
          }
          System.out.println();
      }
  
      // END PATH ALGORITHM 
  
  
      public static void main(String[] args) {
  
          int[] myArr = {5, 3, 1, 4, 8, 2, 6}; 
          // int[] myArr = { 10,32,63,44,115,66,7,18,999 }; // sortedArrayToBST
          BinaryTree myTr = new BinaryTree();
  
          for( int j=0; j &lt; myArr.length; j++){
              myTr.addNode(myArr[j]);
          }
  
          // Node n = BinaryTree.createMinimalBST(myArr);
  
          /*question 4-3
          create a binary tree with minimal height ( balanced tree )*/
          /*myTr.createMinimalBST(myArr);*/
  
          // System.out.println("The root is = "+myTr.root);
          myTr.inOrderTraverseTree(myTr.root);
  
          System.out.println("\n\n");
  
          /*get the height of the binary search tree*/
          /*System.out.println( "the height of the tree is = "+myTr.height(myTr.root));
          System.out.println("\n\n");*/
  
          /*question 4-1
          check whether the tree is balanced */
  
          /*boolean isBalanced = myTr.isBalanced(myTr.root);
          if (isBalanced) {
              System.out.println("The tree is balanced \n\n");
          }*/
  
          /*question 4-4
          create a linked list of all the nodes in the same level of the BST
          breadth first search ( BFS ) is used for implementation */ 
  
          /*ArrayList&lt;LinkedList&lt;Node&gt;&gt; list = createLevelLinkedList(myTr.root);
          printResult(list);*/
  
          /* ge parent of the elements */
          /*
          for(int j = 0; j &lt; myArr.length ; j++){
              int checkParent = myArr[j];
              System.out.println("the parent of "+ checkParent +"  is = "+ myTr.getParent( checkParent) );
          }
          */      
  
          // using an integer value, get the node that contains that int element 
          /*Node myNode = myTr.getNode(44);
          System.out.println("Get my node = "+ myNode.key );  */
  
          /* get in-order successive node of certain node */
          /*int getInOrderSuccessive = 44 ;
          System.out.println( myTr.inorderSucc( myTr.getNode( getInOrderSuccessive)) );*/
  
  
  
          /* question 4-6 
          get the first common ancestor of two nodes */
  
          /*int firstNodeInteger = 7;
          int secondNodeInteger = 66;
          // try the first solution 
          System.out.println( myTr.commonAncestor( myTr.root, myTr.getNode(firstNodeInteger), myTr.getNode(secondNodeInteger) ));
          // try the second solution 
          System.out.println( myTr.commonAncestor2( myTr.root, myTr.getNode(firstNodeInteger), myTr.getNode(secondNodeInteger) ));
          */
  
  
          /* question 4-7 */
          /* check whether one tree is sub-set of the another tree */
          /*      
          int[] array1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13};
          int[] array2 = {2, 4, 5, 8, 9, 10, 11};
  
          Node t1 = myTr.createTreeFromArray(array1);
          Node t2 = myTr.createTreeFromArray(array2);
  
          if (containsTree(t1, t2))
              System.out.println("t2 is a subtree of t1");
          else
              System.out.println("t2 is not a subtree of t1");
  
  
          int[] array3 = {1, 2, 3};
          Node t3 = myTr.createTreeFromArray(array1);
          Node t4 = myTr.createTreeFromArray(array3);
  
          if (containsTree(t3, t4))
              System.out.println("t4 is a subtree of t3");
          else
              System.out.println("t4 is not a subtree of t3");
          */
  
          /*  question 4-8 
          algorithm to get all the paths equal to given value */
  
          /*int testValue  = 7;
          myTr.findSum( myTr.root, testValue );*/
  
      }
  
  }
  </code></pre>