Make delicious recipes!

Printing a tree (like a tree) on console



This may seem like an easy task but is actually non trivial.
Consider the challenges involved:
  1. You cannot return to the previous line once newline character has been printed.
    Due to this, the tree must be printed line by line.
    Even the bars used to connect the nodes must be printed line by line.

  2. The distance between the nodes is minimum at the leaf level and goes on increasing as we move upward.
    To accommodate this increased distance, the vertical separation between the levels also increases as we move upward.

  3. If some branch is missing in the middle of the tree, the spaces for the right siblings should not get affected due to absence of printing for the missing siblings.

  4. The number of digits contained in the treeNode.data should also be taken into account for a better symmetry of the tree.



With the above considerations in mind, the following Java code can be written to approximately print a binary tree.


import java.util.*;

public class TreeNode {

    public int idata;
    
    public TreeNode left;
    public TreeNode right;
    public TreeNode parent;
    
    // variables needed to print the tree like a tree
    int depth=0;
    int level=0;
    int drawPos=0;
    

    /******** Functions to create a random binary search tree *********/
    
    public static int RANDOM_RANGE = 1000;
    
    public static TreeNode createRandomIntegerTree (int numNodes)
    {
        RANDOM_RANGE = 10*numNodes;
        
        TreeNode root = new TreeNode ();
        root.idata = (int)(Math.random()*RANDOM_RANGE);
        
        int treeSize = countNodes(root);
        while (treeSize < numNodes)
        {
            int count = numNodes - treeSize;
            while (count-- > 0)
                root.insertInteger((int)(Math.random()*RANDOM_RANGE));
            treeSize = countNodes (root);
        }
        return root;
    }
    
    
    // Inserts a given number into the BST
    void insertInteger(int data) 
    {
        if (this.idata == data)
            return;
        if (this.idata < data)
        {
            if (this.right == null)
            {
                this.right = new TreeNode();
                this.right.idata = data;
                this.right.parent = this;
            }
            else
            {
                this.right.insertInteger(data);
            }
        }
        else
        {
            if (this.left == null)
            {
                this.left = new TreeNode();
                this.left.idata = data;
                this.left.parent = this;
            }
            else
            {
                this.left.insertInteger(data);
            }
        }
    }
    
    

    // Creates a random tree and prints it like a tree
    public static void main(String[] args) 
    {
        TreeNode root = createRandomIntegerTree(20);
        root.inOrderInteger(", ");
        drawTree (root);
    }


    /************ Actual functions that print the tree like a tree ********************/
    static void drawTree(TreeNode root) 
    {
        
        System.out.println("\n\nLevel order traversal of tree:");
        int depth = depth(root);
        setLevels (root, 0);
        
        int depthChildCount[] = new int [depth+1];
        
        
        LinkedList<TreeNode> q = new  LinkedList<TreeNode> ();
        q.add(root.left);
        q.add(root.right);
        
        // draw root first
        root.drawPos = (int)Math.pow(2, depth-1)*H_SPREAD;
        currDrawLevel = root.level;
        currSpaceCount = root.drawPos;
        System.out.print(getSpace(root.drawPos) + root.idata);
        
        while (!q.isEmpty())
        {
            TreeNode ele = q.pollFirst();
            drawElement (ele, depthChildCount, depth, q);
            if (ele == null)
                continue;
            q.add(ele.left);
            q.add(ele.right);
        }
        System.out.println();
    }
    
    static int currDrawLevel  = -1;
    static int currSpaceCount = -1;
    static final int H_SPREAD = 3; 
    static void drawElement(TreeNode ele, int depthChildCount[], int depth, LinkedList<TreeNode> q) 
    {
        if (ele == null)
            return;
        
        if (ele.level != currDrawLevel)
        {
            currDrawLevel = ele.level;
            currSpaceCount = 0;
            System.out.println();
            for (int i=0; i<(depth-ele.level+1); i++)
            {
                int drawn = 0;
                if (ele.parent.left != null)
                {
                    drawn = ele.parent.drawPos - 2*i - 2;
                    System.out.print(getSpace(drawn) + "/");
                }
                if (ele.parent.right != null)
                {
                    int drawn2 = ele.parent.drawPos + 2*i + 2;
                    System.out.print(getSpace(drawn2 - drawn) + "\\");
                    drawn = drawn2;
                }
                
                TreeNode doneParent = ele.parent;
                for (TreeNode sibling: q)
                {
                    if (sibling == null)
                        continue;
                    if (sibling.parent == doneParent)
                        continue;
                    doneParent = sibling.parent;
                    if (sibling.parent.left != null)
                    {
                        int drawn2 = sibling.parent.drawPos - 2*i - 2;
                        System.out.print(getSpace(drawn2-drawn-1) + "/");
                        drawn = drawn2;
                    }
                    
                    if (sibling.parent.right != null)
                    {
                        int drawn2 = sibling.parent.drawPos + 2*i + 2;
                        System.out.print(getSpace(drawn2-drawn-1) + "\\");
                        drawn = drawn2;
                    }
                }
                System.out.println();
            }
        }
        int offset=0;
        int numDigits = (int)Math.ceil(Math.log10(ele.idata));
        if (ele.parent.left == ele)
        {
            ele.drawPos = ele.parent.drawPos - H_SPREAD*(depth-currDrawLevel+1);
            //offset = 2;
            offset += numDigits/2;
        }
        else
        {
            ele.drawPos = ele.parent.drawPos + H_SPREAD*(depth-currDrawLevel+1);
            //offset = -2;
            offset -= numDigits;
        }
        
        System.out.print (getSpace(ele.drawPos - currSpaceCount + offset) + ele.idata);
        currSpaceCount = ele.drawPos + numDigits/2;
    }

    
    // Utility functions
    public void inOrderInteger (String sep)
    {
        if (left != null)
            left.inOrderInteger(sep);
        System.out.print(idata + sep);
        if (right != null)
            right.inOrderInteger(sep);
    }
    
    public static int depth (TreeNode n)
    {
        if (n == null)
            return 0;
        n.depth = 1 + Math.max(depth(n.left), depth(n.right));
        return n.depth;
    }
    
    
    public static int countNodes (TreeNode n)
    {
        if (n == null)
            return 0;
        return 1 + countNodes(n.left) + countNodes(n.right);
    }
    
    static void setLevels (TreeNode r, int level)
    {
        if (r == null)
            return;
        r.level = level;
        setLevels (r.left, level+1);
        setLevels (r.right, level+1);
    }

    static String getSpace (int i)
    {
        String s = "";
        while (i-- > 0)
            s += " ";
        return s;
    }

}



Sample Execution 1:
31, 33, 35, 43, 55, 65, 69, 70, 88, 89, 115, 122, 127, 129, 139, 155, 179, 181, 184, 187, 

Level order traversal of tree:
                                             33
                                           /    \
                                         /        \
                                       /            \
                                     /                \
                                   /                    \
                                 /                        \
                               /                            \
                         31                                      122
                                                                /    \
                                                              /        \
                                                            /            \
                                                          /                \
                                                        /                    \
                                                      /                        \
                                                 65                                179
                                              /    \                               /   \
                                            /        \                           /       \
                                          /            \                       /           \
                                        /                \                   /               \
                                      /                    \               /                   \
                                  35                          115      139                          184
                                   \                         /     /   \                         /   \
                                     \                     /     /       \                     /       \
                                       \                 /     /           \                 /           \
                                         \             /     /               \             /               \
                                           55      89      127                    155      181                    187
                                           /     /         \
                                         /     /             \
                                       /     /                 \
                                     43      70                    129
                                        /    \
                                      /        \
                                     69         88



Sample Execution 2:
5, 14, 23, 68, 70, 71, 79, 83, 87, 96, 98, 119, 

Level order traversal of tree:
                                            96
                                          /    \
                                        /        \
                                      /            \
                                    /                \
                                  /                    \
                                /                        \
                              /                            \
                       5                                        98
                         \                                         \
                           \                                         \
                             \                                         \
                               \                                         \
                                 \                                         \
                                   \                                         \
                                       14                                      119
                                           \
                                             \
                                               \
                                                 \
                                                   \
                                                      71
                                                      /    \
                                                    /        \
                                                  /            \
                                                /                \
                                             68                     79
                                          /    \                       \
                                        /        \                       \
                                      /            \                       \
                                    23               70                     87
                                                                           /
                                                                         /
                                                                        83




Sample Execution 3:
19, 23, 24, 33, 36, 39, 44, 46, 90, 95, 99, 103, 

Level order traversal of tree:

                           23
                         /    \
                       /        \
                     /            \
                   /                \
                 /                    \
               /                        \
             /                            \
       19                                       24
                                                  \
                                                    \
                                                      \
                                                        \
                                                          \
                                                            \
                                                                39
                                                                /    \
                                                              /        \
                                                            /            \
                                                          /                \
                                                        /                    \
                                                    36                           99
                                                 /                             /   \
                                               /                             /       \
                                             /                             /           \
                                           /                             /               \
                                        33                              90                    103
                                                                   /    \
                                                                 /        \
                                                               /            \
                                                             46               95
                                                          /
                                                        /
                                                       44




Sample Execution 4:
1, 8, 30, 31, 42, 66, 74, 76, 90, 91, 107, 112, 

Level order traversal of tree:

                1
                  \
                    \
                      \
                        \
                          \
                            \
                                42
                                /    \
                              /        \
                            /            \
                          /                \
                        /                    \
                    30                           76
                 /    \                         /   \
               /        \                     /       \
             /            \                 /           \
           /                \             /               \
       8                      31      66                     91
                                       \                   /   \
                                         \               /       \
                                           \           /           \
                                            74      90              107
                                                                        \
                                                                          \
                                                                         112




Sample Execution 5:
6, 16, 19, 27, 41, 52, 56, 60, 67, 69, 87, 102, 

Level order traversal of tree:
                                                41
                                              /    \
                                            /        \
                                          /            \
                                        /                \
                                      /                    \
                                 6                            56
                                   \                         /   \
                                     \                     /       \
                                       \                 /           \
                                         \             /               \
                                           19      52                     69
                                           /    \                         /   \
                                         /        \                     /       \
                                       /            \                 /           \
                                     16               27            60              102
                                                                    \             /
                                                                      \         /
                                                                      67      87








Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal