If we do a level order traversal of tree such that the left 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 left view of tree. This can be done by doing a level order 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 printLeftViewLevelOrder(currentNode = root)
2. In function printLeftViewLevelOrder if currentNode is null, do nothing and return.
3. Else, add tuple (node = currentNode, level = 0) to the '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 left most) node for this new level and therefore we print currentNode's value and update maxLevelSeenSoFar to level.
- if left child of currentNode is not null then we add tuple (currentNode.left, level + 1) to 'queue'.
- if right child of currentNode is not null then we add tuple (currentNode.right, level + 1) to 'queue'.
* Please note that we are adding left child of node to the 'queue' before right child to make sure that the left-most node at any level is visited before other nodes at that level.
After execution of step #4, left 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 left-most node of any given level is visited before other nodes in that level. This can be easily achieved by visiting left sub-tree of node before right sub-tree. Basically, in this traversal, we visit the node first, then visit the left sub-tree and finally the right sub-tree(N-L-R).
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 printLeftView(currentNode = root, level = 0)
2. In function printLeftView(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 printLeftView(currentNode.left, level + 1) to make sure nodes in the left sub-tree are visited.
d. Make a recursive call printLeftView(currentNode.right, level + 1) to make sure nodes in the right sub-tree are visited.
** Notice that while visiting nodes with recursive calls, printLeftView(currentNode.left, level + 1) is called before printLeftView(currentNode.right, level + 1) in order to make sure that for any node, left sub-tree of that node is visited before right sub-tree. This guarantees that at any level, the left-most node is visited before other nodes at that level.
After execution of step #2, left view of tree would be printed.
Please checkout code snippet and algorithm visualization section for more details of the algorithm.