How to display binary search tree rotated 90deg which starts from lowest point

Question

I have created a Binary Search Tree as follows:

static class TreeNode{
    private int data;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int data){
        this.data=data;
    }

    public void add(int data){
        if( data >= this.data){
            if(this.rightChild == null){
                this.rightChild = new TreeNode(data);
            }else{
                this.rightChild.add(data);
            }
        }else {
            if(this.leftChild == null){
                this.leftChild = new TreeNode(data);
            }else {
                this.leftChild.add(data);
            }
        }
    }

    public int getData(){
        return data;
    }
    public  void setLeftChild(TreeNode leftChild){
        this.leftChild = leftChild;
    }
    public  void setRightChild(TreeNode rightChild){
        this.rightChild = rightChild;
    }
    public TreeNode getLeftChild(){
        return leftChild;
    }
    public TreeNode getRightChild(){
        return rightChild;
    }
    public void print() {
        print("", this, false);
    }

    public void print(String prefix, TreeNode n, boolean isLeft) {
        if (n != null) {
            System.out.println (prefix + (isLeft ? "|-- " : "\\-- ") + n.data);
            print(prefix + (isLeft ? "|   " : "    "), n.leftChild, true);
            print(prefix + (isLeft ? "|   " : "    "), n.rightChild, false);
        }
    }
}

static class BinaryTree{

  private TreeNode root;

  public void pprint(){
      traversePreOrder(this.root);
  }

  public void traversePreOrder(TreeNode node) {
      if (node != null) {
          System.out.print(" " + node.data);
          traversePreOrder(node.leftChild);
          traversePreOrder(node.rightChild);
      }
  }
}

I want to display my tree, however not normally, but in rotated 90deg, which starts from the lowest point.

For example: if the input is: 901 292 247 997 457 468 216 82 530 524 793 952 730 764 820 460 424

The output should look like this:

Another Example: if the input is: 302 946 638 376 604 610 45 547 76 347 694 495 51 130 159

Output:

P.S I tried with the information in How to print binary tree diagram in Java, but I was unable to solve the issue :(

Answer 1

Some observations:

• If you want the nodes to show up at the correct positions, you must use in-order traversal in your recursive function: Descend left, then print, then descend right.

• There is no constant prefix for each node. In your second example, when you go left from 76, you must print the connection between 76 and 45, but if you go right, there is no connection at the same depth.

  You can solve this by keeping a history of directions, for example as string of L's and R's.

• Each node has a "postfix" that depends on whether it has a left or right child or both.

• The numbers must be padded to a fixed width, so that the "postfix" lines up with the connections.

I don't speak Java, but here's some Javascript-like pseudocode that sould achieve what you want:

function tree_print(n, path) {
    if (n) {
        // determine prefix

        let prefix = "";

        if (path.length > 0) {
            for (let i = 1; i < path.length; i++) {
                prefix += (path[i] == path[i - 1]) ? "     "
                                                   : "    │";
            }
            
            prefix += (path[path.length - 1] == "L") ? "    ┌"
                                                     : "    └";
        }

        // determine postfix
        
        let post = 0;
        if (n.left) post |= 1;
        if (n.right) post |= 2;

        let postfix = " ┘┐┤"[post];
    
        tree_print(n.left, path + "L");
        print(prefix + pad(n.value) + postfix);
        tree_print(n.right, path + "R");
    } 
}

Call it (hypothetically) with:

tree_print(root, "");

Answer 2

Some issues:

• You should not need to pass a node instance as argument when you already have the current (this) instance.

• pprint never calls the print method on the TreeNode class

• The print method on the TreeNode class visits the nodes in pre-order. For in-order, you should first visit the left subtree, then the node itself and then the right subtree

Here is a correction to the print methods in TreeNode:

class TreeNode{

    /* ... constructor and other methods here ... */

    public void print() {
        print("", "", "", "");
    }

    public void print(String prefix, String left, String mid, String right) {
        String indent = " ".repeat(String.valueOf(data).length());
        if (leftChild != null) {
            leftChild.print(prefix + left + indent, " ", "┌", "│");
        }
        System.out.println(prefix + mid + data 
                           + " ┐┘┤".charAt((leftChild  != null ? 2 : 0) 
                                         + (rightChild != null ? 1 : 0)));
        if (rightChild != null) {
            rightChild.print(prefix + right + indent, "│", "└", " ");
        }
    }
}

And in BinaryTree we would simply defer the job to the TreeNode class:

class BinaryTree {
    private TreeNode root;

    public void pprint() {
        if (root != null) {
            root.print();
        }
    }

    public void add(int data) {
        if (root == null) {
            root = new TreeNode(data);
        } else {
            root.add(data);
        }
    }
}