Print a Binary Tree in Vertical Order

Yesterday morning while looking at the news on my phone, I ran into Print a Binary Tree in Vertical Order | Set 2 (Map based Method) by GeeksforGeeks. Without reading the article I just twitted it. I tend to do this with software related articles that call my attention. That way I can go through my Twitter history and read such articles when I have enough time to do so.

By 07:00 AM I was down in my home office ready to experiment and have fun. Most weekend days I work one 2-hour block, buy yesterday my wife and a couple friends were getting together to catch up on things. They sit outdoors on the deck of the house of the gal hosting the gathering in order to keep social distancing due to the COVID-19 pandemic. Since we live in the Twin Cities of Minneapolis and St. Paul, such gatherings should be coming to an end shortly. The high temperature for the following two weeks is forecasted to be in the mid to upper 40’s. That said; today I have enough time for two blocks!!!

On a separate note, this morning I read (not just posted on Twitter) the article Harvard professor Charles Lieber, charged federally for ties to China, wants school to pay his legal bills. The article covers his legal problems, associated with mostly Ivy League school professors, with disclosing / selling information and then attempting to avoid paying taxes in the USA. He was part of the Thousand Talents Program organize and sponsored by the Chinese Communist Party (CCP) government to help China improve on their higher education system.

I know a few people that are or have been  in the program. Most people sign up for two years. Very few stay longer. I know that Chinese laws mandate that such individuals must spent 50% of their income in China. Not sure how the remaining 50% can be transferred to a different country or how such income is taxed.

This is not the only person that has been caught. It seems there are many cases that have been reported in the news with little fanfare. If interested, do some searches on the web and educate yourself about this one more problem / threat to the free world by the CCP.

Please note that in my posts I always refer to the CCP and not to the Chinese people, which in many cases are enslaved by the CCP, prosecuted, tortured and may go missing permanently if they do not obey when asked to do who knows what.

I wanted to finish this post yesterday, but I was just able to experiment with my solution. I will go back at some time and see if I can come up with an alternate solution and read the one from GeeksforGeeks.

If interested in the subject, please visit the article Print a Binary Tree in Vertical Order and read enough to understand the objective (requirements) and give it a try.

I will use the Java programming language, the VSCode IDE running on a Windows 10 computer. Because I like to develop the code locally on my computer, I need a test scaffolding. I will not describe in detail the test scaffolding. I will only touch on a couple functions that I wrote to check if the binary tree was properly built. The entire code, including the test scaffolding, is in the associated GitHub repository.

The GeeksforGeeks web site has a couple diagrams describing a sample case. I suggest that before going any further you read enough from the article and take a look at the diagrams in order to crystallize the requirements.

1,2,3
main <<< inOrder: 2 1 3 
main <<< bfs: 
1 
2 3 
main <<< binary tree in vertical order:
printBTVerticalOrder <<< dists: {1=0, 2=-1, 3=1}
[2]
[1]
[3]


1,2,3,4,5,6,7,null,null,null,null,null,8,null,9
main <<< inOrder: 4 2 5 1 6 8 3 7 9 
main <<< bfs: 
1 
2 3 
4 5 6 7 
8 9 
main <<< binary tree in vertical order:
printBTVerticalOrder <<< dists: {1=0, 2=-1, 3=1, 4=-2, 5=0, 6=0, 7=2, 8=1, 9=3}
[4]
[2]
[1, 5, 6]
[3, 8]
[7]
[9] 


1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
main <<< inOrder: 8 4 9 2 10 5 11 1 12 6 13 3 14 7 15 
main <<< bfs: 
1 
2 3 
4 5 6 7 
8 9 10 11 12 13 14 15 
main <<< binary tree in vertical order:
printBTVerticalOrder <<< dists: {1=0, 2=-1, 3=1, 4=-2, 5=0, 6=0, 7=2, 8=-3, 9=-1, 10=-1, 11=1, 12=-1, 13=1, 14=1, 15=3}     
[8]
[4]
[2, 9, 10, 12]
[1, 5, 6]
[3, 11, 13, 14]
[7]
[15]

The input (first) line contains the nodes for a binary tree in depth first search order.

After reading the data and generating a representation of the binary tree, we perform an in-order traversal and then a breadth first traversal to make sure all is well with our binary tree.

Finally, it seems we display the binary tree in vertical order. In the first example, node 2 is leftmost, then node 1 is center, and node 3 is rightmost.

The Full and Complete Binary Tree document contains descriptions and formulas for binary trees.

The second example is the one provided by GeeksforGeeks. As you can see in the breadth first representation, each level of the binary tree holds as many nodes as possible.

/**
  * Definition for a binary tree node.
  */
class TreeNode {
    
    // **** class members ****
    int         val;
    TreeNode    left;
    TreeNode    right;
    
    // **** constructors ****
    TreeNode() {}
    
    TreeNode(int val) { this.val = val; }
    
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
  
    // **** ****
    @Override
    public String toString() {
        return "" + this.val;
    }
}

While editing this post, I noticed that my notes, which are generated in a different machine, did not include the definition of the TreeNode class. This is the commonly used class on binary tree problems by LeetCode.

    /**
     * Test scaffolding
     */
    public static void main(String[] args) {
        
        // **** open scanner ****
        Scanner sc = new Scanner(System.in);

        // **** read and split the data for the binary tree ****
        String[] data = sc.nextLine().trim().split(",");

        // **** close scanner ****
        sc.close();

        // **** binary tree ****
        TreeNode bt = null;

        // **** populate the binary tree ****
        bt = populateTree(data);

        // ???? ????
        System.out.print("main <<< inOrder: ");
        inOrder(bt);
        System.out.println();

        // ???? ????
        System.out.println("main <<< bfs: ");
        bfs(bt);

        // **** print binary tree in vertical order ****
        System.out.println("main <<< binary tree in vertical order:");
        printBTVerticalOrder(bt);
    }

The test scaffolding is easy to follow. We open a scanner, read and split the input line into an array of strings each holding an integer. We are done with the scanner so we close it.

We then populate the binary tree. How we do it is out of the main scope of the approach to solve the problem, so we will not cover the process in detail. The complete code is in my GitHub repository. If interested, explanations can be found in older posts dealing with binary trees.

Once we have the binary tree, we perform two traversals displaying the value of the nodes. Given the numbers in the input line, the bfs approach is simpler to visualize.

Finally we call the printBTVerticalOrder() function to print the nodes of our binary tree in vertical order. This is the function of interest.

    /**
     * Traverse the specified binary tree displaying the values in depth first
     * search order.
     * This method is used to verify that the binary tree was properly generated.
     */
    static void inOrder(TreeNode root) {
    
        // **** base case ****
        if (root == null)
            return;
    
        // **** visit the left sub tree ****
        inOrder(root.left);
    
        // **** display the value of this node ****
        System.out.print(root.val + " ");
    
        // **** visit the right sub tree ****
        inOrder(root.right);
    }

The inOrder() function traverses the nodes in the binary tree in order. This means that for each node, we will first traverse the left child, then the node, and finally the right child. We will do this for each and every node in the binary tree. If the binary tree would be a binary search tree, the results would appear in monotonically ascending order. None of the examples are binary search trees.

   /**
     * Traverse the specified binary tree displaying the values in breadth-first 
     * order.
     * This method is used to verify that the binary tree was properly generated.
     */
    static void bfs(TreeNode root) {

        // **** initialize queues ****
        Queue<TreeNode> q       = new LinkedList<TreeNode>();
        Queue<TreeNode> nextQ   = new LinkedList<TreeNode>();

        // **** prime the queue ****
        q.add(root);

        // **** loop displaying and inserting nodes into the queue ****
        while (!q.isEmpty()) {

            // **** get the next node from the queue ****
            TreeNode node = q.remove();

            // **** display the node value ****
            System.out.print(node.val + " ");

            // **** push into the next queue the left child (if needed) ****
            if (node.left != null)
                nextQ.add(node.left);

            // **** push into the next queue the right child (if needed) ****
            if (node.right != null)
                nextQ.add(node.right);
        
            // **** switch queues ****
            if (q.isEmpty()) {

                // **** mark end of level ****
                System.out.println();

                // **** point to the next queue ****
                q = nextQ;

                // **** clear the next queue ****
                nextQ  = new LinkedList<TreeNode>();
            }
        }
    }

The bfs() function traverses a binary tree one level at a time. If you look at the examples, all the nodes at each level are printed in the same line.

We need to declare two queues. Queue q will be the current queue from which we pull out nodes to display. The queue nextQ will be used to store child nodes while traversing each level. At some point we will switch queues and will repeat until done.

To start the process we prime the q with the root node for the binary tree. We are now ready to start the breadth first traversal.

We loop while there are nodes in the q. We remove the next node from the q. We display its value. We then push the left and then the right child (if present) into the nextQ.

We then check if q is empty. In the first pass the q will be empty because we only inserted the root node for the binary tree.

If empty, we display a EOL character, point to the nextQ which at this time may or may not have nodes depending on the left and right child of the root node of our binary tree. We then clear the contents of the nextQ because we might have to repeat the process as we descend into the different levels in our binary tree.

Back at the top of the while loop, we continue is the q is not empty. In all three examples, we will find a node in the q. We repeat the process until there are no more nodes in the q. This will happen after we process the last level in our binary tree.

    // **** node distance to the center (root) of the binary tree ****
    static HashMap<Integer, Integer> dists = new HashMap<Integer, Integer>();

We define a hash map. The idea is to populate for each horizontal distance from the root (center), a list of nodes that share the same value. In the first example we would have a hash map with three entries. You should be able to figure out the values in the associated hash maps for the other two examples. Please take the time to make sure all is well so far.

    /**
     * Print Binary Tree in Vertical Order
     * Complexity O(n).
     */
    static void printBTVerticalOrder (TreeNode root) {

        // **** populate the node distances from the root ****
        computeDistance(root, 0);

        // **** hash map of distance, node values ****
        TreeMap<Integer, ArrayList<Integer>> distNode = new TreeMap<>();
        
        // **** traverse the dists hash map ****
        for (Entry<Integer, Integer> dist : dists.entrySet()) {

            // **** for ease of use ****
            int d = dist.getValue();
            int v = dist.getKey();

            // **** update dist-node hash map ****
            ArrayList<Integer> al = distNode.get(d);
            if (al == null) {
                al = new ArrayList<Integer>();
                al.add(v);
                distNode.put(d, al);
            } else {
                al.add(v);
            }
        }

        // **** print binary tree in vertical order ****
        for (Entry<Integer, ArrayList<Integer>> dn : distNode.entrySet())
            System.out.println(dn.getValue().toString());
    }

We start by computing the horizontal distance from the root for each node in the binary tree. The root node is assigned distance 0, the left child of the root node is at distance -1 (left) and the right child at distance +1. Will check out the computeDistance() function shortly.

We declare the distNode tree map. For each entry as a specified distance, we will add to the associated list the nodes that share the same distance value.

We now traverse the dists hash map and for each entry we get the horizontal distance from the root node and the name (value) of the node in the binary tree. With the information at hand we populate the distNode tree map. If the distance is not available, we add the distance and to the associated array list we add the value of the node in the binary tree. If the distance and the array list are present, we just add the node value to the array list.

When done with the loop we traverse the distNode tree map displaying the values of the array lists. Since we use a tree map the distances will appear in monotonically ascending order.

    /**
     * Compute the horizontal distance from the root for each node.
     * Recursive call.
     * BFS approach.
     * Complexity O(n)
     */
    static void computeDistance(TreeNode root, int dist) {

        // **** base case ****
        if (root == null)
            return;

        // **** store the distance for this node ****
        dists.put(root.val, dist);

        // **** visit left node ****
        computeDistance(root.left, dist - 1);

        // **** visit right node ****
        computeDistance(root.right, dist + 1);
    }

The computeDistance() function computes the horizontal distance for each node from the root node. Distances to the left are negative while distances to the right are positive. The root node sits at distance zero. This is a recursive function. Take a look at the inOrder() function earlier in this post and compare the similarities. Both are recursive so they have a base case to stop recursion. The computeDistance() function represents a pre order traversal, while the inOrder() function represents an in-order binary tree traversal.

Hope you enjoyed solving this exercise as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!

One last thing, many thanks to all 3111 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy.

John

E-mail:  john.canessa@gmail.com