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
Preparing for interviews? IDeserve team is here to help.
Create your profile
Create your profile, and here is what you will get:
1: Interview practice platform.
2: Once you are ready to take the interview, IDeserve team will help you get connected to the best job opportunities.
3: Personalized mentorship from IDeserve team once your interview process has started.
Creation of profile shouldn't take more than 2 minutes.
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.
Support us by whitelisting IDeserve in your ad-blocker.