Left and Right Views in a Binary Tree

Right View – All the nodes visible when viewed from the right side of a tree.

Left View – All the nodes visible when viewed from the left side of a tree.

Consider a simple example below. Notice the views.

Consider another example below where the root node A does not have left subtree. Notice the left and right views.

One of the method is to do a Level Order Traversal on the tree to get the views.
Left View – When we do a level order traversal, notice that the first element in each level gives the left view of the tree.

Right View – When we do a level order traversal, notice that the last element in each level gives the right view of the tree.

Implementation: Recursive solution

Logic:

One way to solve this problem is by doing Level Order Traversal.

1. Keep track of each level starting with level = 1.
2. Store the last node in each level. Use a list or array to store the last node in each level.

Before we jump into coding, let’s understand little bit of the logic here. In each recursive traversal, we check if the current level is greater than the number of nodes in the right view that is encountered. If that is true, then append the last node to the list in the current level.

let right_view_nodes = []

When level = 1, right_view_nodes is initially empty [], then we add the last node in this level which is A, go to the next level.

level = 2, right_view_nodes will have [‘A’], then we add the last node in this level which is C

level = 3, right_view_nodes will have [‘A’, ‘C’], then we add the last node in this level which is G.

level = 4, right_view_nodes will have [‘A’, ‘C’, ‘G’], then we add the last node in this level which is K.

level = 5, right_view_nodes will have [‘A’, ‘C’, ‘G’, ‘K’], then we add the last node in this level which is N.

Basically, as long as the current level > len(right_view_nodes) or len(right_view_nodes) < level, we continue to append the last node at each level to the list.

Code:

def treeTraversal(root, right_view_nodes, level):
    """
    :param obj root: root node of the tree to be traversed.
    :param list right_view_nodes: list of the nodes in the right view.
    :param int level: current level of the tree.
    :return:
    """
    if root is None:
        return
    if len(right_view_nodes) < level:
        right_view_nodes.append(root.value)
    level = level + 1
    # Right View: traverse right subtree first.
    treeTraversal(root.right, right_view_nodes, level)
    treeTraversal(root.left, right_view_nodes, level)
    # Left View: traverse left subtree first.
    # treeTraversal(root.left, right_view_nodes, level)
    # treeTraversal(root.right, right_view_nodes, level)
def rightView(root):
    """
    :param obj root: root node of the tree to be traversed.
    :return list: right view nodes of the tree.
    """
    right_view_nodes = []
    level = 1
    treeTraversal(root, right_view_nodes, level)
    return right_view_nodes
class TreeNode(object):
    def __init__(self, value):
        self.left = None
        self.right = None
        self.data = value
root = TreeNode('A')
root.left = TreeNode('B')
root.right = TreeNode('C')
root.left.left = TreeNode('D')
root.left.right = TreeNode('E')
root.right.left = TreeNode('F')
root.right.right = TreeNode('G')
root.left.right.left = TreeNode('I')
root.right.left.right = TreeNode('K')
root.left.right.left.left = TreeNode('L')
root.left.right.left.right = TreeNode('M')
root.right.left.right.right = TreeNode('N')
print rightView(root)
# Output
Right View: ['A', 'C', 'G', 'K', 'N']
Left View: ['A', 'B', 'D', 'I', 'L']