If we do a level order traversal of tree such that the right-most node of each level is visited before all other nodes in that level then all we need to do is to print out the first visited node at each level to print the right view of tree. This can be done by doing a level order traversal from right end to left end instead of usual traversal from left end to right end and keeping track of max-level seen so far to find out when the new level starts. As soon as we find out that the new level has started, we print out the current node that is being visited.
The steps for this algorithm are -
1. Initialize maxLevelSeenSoFar to -1 and call printRightViewLevelOrder(currentNode = root)
2. In function printRightViewLevelOrder if currentNode is null, do nothing and return.
3. Else, add tuple (node = currentNode, level = 0) to 'queue'.
4. while 'queue' is not empty do
- remove the first tuple(currentNode, level) from the queue.
- if (level > maxLevelSeenSoFar) then we know that we are starting to traverse a new level and this is the first(and right most) node for this new level and therefore we print currentNode's value and update maxLevelSeenSoFar to level.
- if right child of currentNode is not null then we add tuple (currentNode.right, level + 1) to 'queue'.
- if left child of currentNode is not null then we add tuple (currentNode.left, level + 1) to 'queue'.
* Please note that we are adding right child of node to the 'queue' before left child to make sure that the right-most node in any level is visited before other nodes in that level.
After execution of step #4, right view of tree would be printed.
Notice that this algorithm takes O(n) extra space. With the following algorithm, we can save on extra space.
This algorithm basically uses modified pre-order traversal. In this modified pre-order traversal we make sure that -
a. The right-most node of any given level is visited before other nodes in that level. This can be easily achieved by visiting right sub-tree of node before left sub-tree. Basically, in this traversal, we visit the node first, then visit the right sub-tree and finally the left sub-tree(N-R-L).
b. We print out the node value as soon as we encounter a node in the level that is greater than the maximum level seen so far and update maximum level seen so far to current level.
The steps of this algorithm are as following -
1. Initialize maxLevelSeenSoFar to -1 and call printRightView(currentNode = root, level = 0)
2. In function printRightView(currentNode, level),
a. If currentNode is null, then we do nothing and return.
b. Else, if (level > maxLevelSeenSoFar) we print out the currentNode's value and update maxLevelSeenSoFar to level.
c. Make a recursive call printRightView(currentNode.right, level + 1) to make sure nodes in right sub-tree are visited.
d. Make a recursive call printRightView(currentNode.left, level + 1) to make sure nodes in left sub-tree are visited.
** Notice that while visiting nodes with recursive calls, printRightView(currentNode.right, level + 1) is called before printLeftView(currentNode.left, level + 1) in order to make sure that for any node, right sub-tree of that node is visited before left sub-tree. This guarantees that for any level, the right-most node is visited before other nodes in that level.
After execution of step #2, right view of tree would be printed.
Please checkout code snippet and algorithm visualization section for more details of the algorithm.