Algorithms: Left view of a binary tree.

Algorithms: Left view of a binary tree.
5 (100%) 4 votes

In the algorithm section I am here going to share how to get the left view of the binary tree. For that you must know what is binary tree.

Algorithms: Left view of a binary tree.

Binary tree are the tree where one node can have only two child and cannot have more than two.

Left view means what all nodes are visible to you if you see the tree from the left side. Here look at the below tree

Its left view will be

1 2 4

Here is the code for doing that.

class Node:
   def __init__(self,data):
       self.left = None
       self.right = None
       self.data = data

def left_view(queue, current_level):
   if len(queue) == 0:
       return
   node = queue[0]
   node,level = node[0],node[1]
   queue.pop(0)
   if node.left:
       queue.append([node.left, level+1])
   if node.right:
       queue.append([node.right, level+1])
   if current_level < level: 
       print node.data,
       current_level = current_level + 1
   left_view(queue,current_level)

queue = list()
root = Node(1)
current_level = 0
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.left.left = Node(5)
root.left.left.left.left = Node(6)
root.left.left.right = Node(7)
root.right.right = Node(8)
root.right.right.right = Node(9)
root.right.right.right.left = Node(10)
root.right.right.right.left.right = Node(11)
queue.append([root,0])
left_view(queue,-1)
#1 2 4 5 6 11

What we did here:

We reach a node check if it has left element, if it has we put it in queue and then if it has right put right in it and then call left_view again.

In every Iteration it is going to print the first node of level which will be left view. In this way we get the left view of tree.

First node is checked by the current_height and height associated with node in queue. If current height is less than height with node then it is the first node of that level hence print it. 

So in short it is level order traversal with printing the first node of the level as we get it.

Liked the article please share and subscribe. Want to read more articles like this one. Follow the below link for the same

Algorithms and Data Structures.

 


Gaurav Yadav

Gaurav is a Full Stack Web Developer and Blogger. Sportsperson by heart and loves football. He has experience with various frameworks in php, python and javascript. Loves to explore new frameworks and evolve with the trending technology.

Leave a Reply

Your email address will not be published. Required fields are marked *