Print binary tree in vertical order

Given a binary tree, print the nodes of binary tree grouped together in vertical order. Vertical order of a node is defined using its horizontal distance from the root node. Horizontal distance of root from itself is 0. Horizontal distance of right child of root node is +1 and horizontal distance of left child of root node is -1.

Horizontal distance of node 'n' from root = horizontal distance of its parent from root + 1, if node 'n' is right child of its parent.

Horizontal distance of node 'n' from root = horizontal distance of its parent from root - 1, if node 'n' is left child of its parent.

                3
         4              5
      6     7        8     9
              1
          

In the above tree,
horizontal distance of node 3 is  0
horizontal distance of node 4 is -1
horizontal distance of node 5 is +1
horizontal distance of node 6 is -2
horizontal distance of node 7 is  0
horizontal distance of node 8 is  0
horizontal distance of node 9 is +2
horizontal distance of node 1 is +1

and therefore expected vertical order print for this tree is:
  6
  4
  3  7  8
  5  1
  9

Note that, the requirement is that vertical order should be printed starting from left-most end(node 4 cannot be printed before node 6) and in top down manner(node 1 cannot be printed before node 5 though both have same horizontal distance).

Please checkout the code snippet and algorithm visualization for more details.


Video coming soon!



Subscribe for more updates


Algorithm/Insights

The basic idea that will be used here is a modified level-order traversal where we keep track of the horizontal distance of each node while traversing the tree. And once we know horizontal distance of a node, we add it to the list of nodes which have same horizontal distance as that of current node. This list of nodes is maintained using a treeMap where key is horizontal distance 'd' and value is list of nodes which are at horizontal distance 'd' from the root. A treeMap is modified hashMap where keys are inserted in sorted order. (A treeMap is implemented using Red-Black tree and hence insertion/retrieval takes O(log n) time instead of O(1) time as is the case for a regular hashMap)

The formal algorithm is as following -
1. Initialize verticalOrderMap to an empty treeMap.
2. Call fillUpVerticalOrderMap(currentNode = root, horizontalDistFromRoot = 0, verticalOrderMap = verticalOrderMap);
3. If currentNode == null, return.
4. Initialize queue to an empty queue.
5. Add tuple(currentNode, horizontalDistFromRoot) to queue.
6. While (queue is not empty)
6a. Remove an entry(node, horizontalDistanceOfNode) from queue.
6b. Add node to a list of nodes in verticalOrderMap at key horizontalDistanceOfNode. If list does not exist, create a new list and add this list to verticalOrderMap at key horizontalDistanceOfNode.
6c. Because we don't want to add null nodes to queue, we check of node.left is null. If it is not, we add an entry (node.left, horizontalDistanceOfNode - 1) to queue.
6d. Similar to above step, we add an entry (node.right, horizontalDistanceOfNode + 1) to queue if node.right is not null.
7. After this step, verticalOrderMap is filled and we print out this map.


Algorithm Visualization




Code Snippet

			
package com.ideserve.questions.nilesh;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Map;
import java.util.TreeMap;
import java.util.Map.Entry;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Given a binary tree, print the nodes of binary tree grouped together in vertical order. Vertical order of a node is defined using its horizontal distance from the root node. 
 * @author Nilesh
 */

public class PrintBinaryTreeVerticalOrder {

    class QueueEntry
    {
        TreeNode node;
        int horizontalDistance;
        QueueEntry(TreeNode node, int horizontalDistance)
        {
            this.node = node;
            this.horizontalDistance = horizontalDistance;
        }
    }
    
    class TreeNode
    {
        TreeNode left;
        TreeNode right;
        int val;
    
        public TreeNode(int x)
        {
            this.val = x;
        }
    }
    
    TreeNode root;
    
    private void fillUpVerticalOrderMap(TreeNode currentNode, int horizontalDistFromRoot, Map verticalOrderMap)
    {
        if (currentNode == null) return;
        
        ArrayList<Integer> mapEntry;
        LinkedList<QueueEntry> queue = new LinkedList();
        
        queue.add(new QueueEntry(currentNode, horizontalDistFromRoot));
        
        while (!queue.isEmpty())
        {
            QueueEntry entry = queue.remove();

            // update verticalOrderMap with current node entry
            mapEntry = (ArrayList<Integer>) verticalOrderMap.get(entry.horizontalDistance);
            
            if (mapEntry != null) // if node exists at same horizontal distance from root, update the nodeList
            {
                mapEntry.add(entry.node.val);
                verticalOrderMap.put(entry.horizontalDistance, mapEntry);
            }
            else // create a new list for this horizontal distance
            {
                mapEntry = new ArrayList();
                mapEntry.add(entry.node.val);
                verticalOrderMap.put(entry.horizontalDistance, mapEntry);
            }
            
            // we don't want to adding null nodes into the queue
            if (entry.node.left != null)
            {
                // left child would have horizontal distance = parent's horizontal distance - 1
                queue.add(new QueueEntry(entry.node.left, entry.horizontalDistance - 1));
            }
            
            if (entry.node.right != null)
            {
                // right child would have horizontal distance = parent's horizontal distance + 1
                queue.add(new QueueEntry(entry.node.right, entry.horizontalDistance + 1));
            }
        }
    }
    

    public void printVerticalOrder()
    {
        Map<Integer, ArrayList<Integer>> verticalOrderMap = new TreeMap<>();

        fillUpVerticalOrderMap(root, 0, verticalOrderMap);

        // print map entries to print the top view
        Iterator<Entry<Integer, ArrayList<Integer>>> iterator = verticalOrderMap.entrySet().iterator();

        while (iterator.hasNext())
        {
            Entry<Integer, ArrayList<Integer>> mapEntry = iterator.next();
            ArrayList<Integer> nodeList = mapEntry.getValue();
            for (int i = 0; i < nodeList.size(); i++)
            {
                System.out.print("  " + nodeList.get(i));
            }
            System.out.println("");
        }
    }


    public TreeNode createTree()
    {
        this.root = new TreeNode(3);
        TreeNode n1   = new TreeNode(4);
        TreeNode n2   = new TreeNode(5);
        TreeNode n3   = new TreeNode(6);
        TreeNode n4   = new TreeNode(7);
        TreeNode n5   = new TreeNode(8);
        TreeNode n6   = new TreeNode(9);
        TreeNode n7   = new TreeNode(1);

        root.left  = n1;
        root.right = n2;
        
        n1.left  = n3;
        n1.right = n4;
            
        n2.left  = n5;
        n2.right = n6;
        
        n4.right = n7;

        return root;
    }
    

    public static void main(String[] arg)
    {
        PrintBinaryTreeVerticalOrder tree = new PrintBinaryTreeVerticalOrder();

        /*
                    3
              4           5
            6   7       8   9
                  1
         */

        tree.createTree();
        tree.printVerticalOrder();
    }
}
		

Order of the Algorithm

Time Complexity is O(n.log(n))
Space Complexity is O(n)


Contribution

  • Sincere thanks from IDeserve community to Nilesh More for compiling current post.


    Nilesh More