Given a binary tree, print it vertically. The following example illustrates vertical order traversal.
1
/ \
2 3
/ \ / \
4 5 6 7
\ \
8 9
The output of print this tree vertically will be:
4
2
1 5 6
3 8
7
9
We have discussed a O(n2) solution in the previous post. In this post, an efficient solution based on hash map is discussed. We need to check the Horizontal Distances from root for all nodes. If two nodes have the same Horizontal Distance (HD), then they are on same vertical line. The idea of HD is simple. HD for root is 0, a right edge (edge connecting to right subtree) is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. For example, in the above tree, HD for Node 4 is at -2, HD for Node 2 is -1, HD for 5 and 6 is 0 and HD for node 7 is +2.
We can do preorder traversal of the given Binary Tree.
While traversing the tree, we can recursively calculate HDs. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1. For every HD value, we maintain a list of nodes in a hasp map. Whenever we see a node in traversal, we go to the hash map entry and add the node to the hash map using HD as a key in map.
[pastacode lang=”python” manual=”%23%20Python%20program%20for%20printing%20vertical%20order%20of%20a%20given%0A%23%20binary%20tree%0A%20%0A%23%20A%20binary%20tree%20node%0Aclass%20Node%3A%0A%20%20%20%20%23%20Constructor%20to%20create%20a%20new%20node%0A%20%20%20%20def%20__init__(self%2C%20key)%3A%0A%20%20%20%20%20%20%20%20self.key%20%3D%20key%0A%20%20%20%20%20%20%20%20self.left%20%3D%20None%0A%20%20%20%20%20%20%20%20self.right%20%3D%20None%0A%20%0A%23%20Utility%20function%20to%20store%20vertical%20order%20in%20map%20’m’%20%0A%23%20’hd’%20is%20horizontal%20distance%20of%20current%20node%20from%20root%0A%23%20’hd’%20is%20initially%20passed%20as%200%0Adef%20getVerticalOrder(root%2C%20hd%2C%20m)%3A%0A%20%0A%20%20%20%20%23%20Base%20Case%0A%20%20%20%20if%20root%20is%20None%3A%0A%20%20%20%20%20%20%20%20return%0A%20%20%20%20%20%0A%20%20%20%20%23%20Store%20current%20node%20in%20map%20’m’%0A%20%20%20%20try%3A%0A%20%20%20%20%20%20%20%20m%5Bhd%5D.append(root.key)%0A%20%20%20%20except%3A%0A%20%20%20%20%20%20%20%20m%5Bhd%5D%20%3D%20%5Broot.key%5D%0A%20%20%20%20%20%0A%20%20%20%20%23%20Store%20nodes%20in%20left%20subtree%0A%20%20%20%20getVerticalOrder(root.left%2C%20hd-1%2C%20m)%0A%20%20%20%20%20%0A%20%20%20%20%23%20Store%20nodes%20in%20right%20subtree%0A%20%20%20%20getVerticalOrder(root.right%2C%20hd%2B1%2C%20m)%0A%20%0A%23%20The%20main%20function%20to%20print%20vertical%20order%20of%20a%20binary%0A%23tree%20ith%20given%20root%0Adef%20printVerticalOrder(root)%3A%0A%20%20%20%20%20%0A%20%20%20%20%23%20Create%20a%20map%20and%20store%20vertical%20order%20in%20map%20using%0A%20%20%20%20%23%20function%20getVerticalORder()%0A%20%20%20%20m%20%3D%20dict()%0A%20%20%20%20hd%20%3D%200%0A%20%20%20%20getVerticalOrder(root%2C%20hd%2C%20m)%0A%20%20%20%20%20%0A%20%20%20%20%23%20Traverse%20the%20map%20and%20print%20nodes%20at%20every%20horizontal%0A%20%20%20%20%23%20distance%20(hd)%0A%20%20%20%20for%20index%2C%20value%20in%20enumerate(sorted(m))%3A%0A%20%20%20%20%20%20%20%20for%20i%20in%20m%5Bvalue%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20print%20i%2C%0A%20%20%20%20%20%20%20%20print%0A%20%0A%20%0A%23%20Driver%20program%20to%20test%20above%20function%0Aroot%20%3D%20Node(1)%0Aroot.left%20%3D%20Node(2)%0Aroot.right%20%3D%20Node(3)%0Aroot.left.left%20%3D%20Node(4)%0Aroot.left.right%20%3D%20Node(5)%0Aroot.right.left%20%3D%20Node(6)%0Aroot.right.right%20%3D%20Node(7)%0Aroot.right.left.right%20%3D%20Node(8)%0Aroot.right.right.right%20%3D%20Node(9)%0Aprint%20%22Vertical%20order%20traversal%20is%22%0AprintVerticalOrder(root)%0A%20%0A%23%20This%20code%20is%20contributed%20by%20Nikhil%20Kumar%20Singh(nickzuck_007)” message=”Python Program” highlight=”” provider=”manual”/]Output:
Vertical order traversal is 4 2 1 5 6 3 8 7 9
Time Complexity of hashing based solution can be considered as O(n) under the assumption that we have good hashing function that allows insertion and retrieval operations in O(1) time. In the above C++ implementation, map of STL is used. map in STL is typically implemented using a Self-Balancing Binary Search Tree where all operations take O(Logn) time. Therefore time complexity of above implementation is O(nLogn).
[ad type=”banner”]Note that the above solution may print nodes in same vertical order as they appear in tree. For example, the above program prints 12 before 9. See this for a sample run.
1
/ \
2 3
/ \ / \
4 5 6 7
\ / \
8 10 9
\
11
\
12