oreillsf oreillsf - 3 days ago 5
Java Question

java Printing inorder BST with parenthesis

I want to return a String containing all keys in the tree, in the order they are stored. The keys in each subtree should be contained in a parenthesis.

_7_
/ \
_3_ 8
/ \
1 6
\ /
2 4
\
5


The output for this BST should be
(((()1(()2()))3((()4(()5()))6()))7(()8()))
.
My code for doing this is:

public String printKeysInOrder() {
if (isEmpty()) {
return "()";
}

printInOrderRec(root);

System.out.print(sb.toString());
return sb.toString();
}

StringBuilder sb = new StringBuilder();

private String printInOrderRec(Node root) {
if (root == null) {
return null;
}
sb.append("(");
printInOrderRec(root.left);
sb.append("(");
sb.append(")");

sb.append(root.val);

printInOrderRec(root.right);

return null;
}


Which gives me the output:
(((()1(()2()3((()4(()5()6()7(()8
.
I have been working on this for ages and can't figure out where and how to append the missing brackets. Any help would be appreciated.

Answer

Before jumping into coding solution, let's try to draw how the output should be can be generated.

(--------------------------------7-------)
 (------------3-----------------) (--8--)
  (--1-------) (------------6--)   () ()
   () (--2--)   (--4-------) ()
       () ()     () (--5--)
                     () ()

Here every enclosed pair of parentheses defines a call stack. I am not trying to describe each call stack, otherwise this answer would be arbitarily long. However, from the drawing we can find out 5 portions at each call stack.

  1. Left paranthesis
  2. Left child
  3. Value
  4. Right child
  5. Right paranthesis

So, the your printInOrderRec method may look like:

private void printInOrderRec(Node root) {
    sb.append("(");
    if (root != null) {
        printInOrderRec(root.left);
        sb.append(root.val);
        printInOrderRec(root.right);
    }
    sb.append(")");
}

Note: I have made the return type void because in your code it returns nothing but null.

Comments