Left View of Binary Tree

Given a Binary Tree, print Left view of it. Left view of a Binary Tree is set of nodes visible when tree is visited from Left side. The task is to complete the function leftView(), which accepts root of the tree as argument.

Left view of following tree is 1 2 4 8.

1
/ \
2 3
/ \ / \
4 5 6 7
\
8

Example 1:

Input:
1
/ \
3 2
Output: 1 2 3

code:

val = []
def leftView_util(root, level, Elements_at_levels):
if root is None:
return
if level not in Elements_at_levels:
Elements_at_levels[level] = root.data
leftView_util(root.left, level + 1, Elements_at_levels)
leftView_util(root.right, level + 1, Elements_at_levels)
def leftView(root):
Elements_at_levels = {}
leftView_util(root, 1, Elements_at_levels)
for i in range(1, len(Elements_at_levels) + 1):
val.append(Elements_at_levels[i])
leftView(b)
print(val)

test with this:

class BstNode:
def __init__(self, key):
self.data = key
self.right = None
self.left = None
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
"""Returns list of strings, width, height, and horizontal coordinate of the root."""
# No child.
if self.right is None and self.left is None:
line = '%s' % self.data
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle

# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = '%s' % self.data
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s
second_line = x * ' ' + '/' + (n - x - 1 + u) * ' '
shifted_lines = [line + u * ' ' for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2

# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = '%s' % self.data
u = len(s)
first_line = s + x * '_' + (n - x) * ' '
second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' '
shifted_lines = [u * ' ' + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2

# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = '%s' % self.data
u = len(s)
first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' '
second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' '
if p < q:
left += [n * ' '] * (q - p)
elif q < p:
right += [m * ' '] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
b = BstNode(10)
b.left = BstNode(20)
b.right= BstNode(30)
b.right.right = BstNode(100)
b.right.right.right = BstNode(110)
b.right.right.right.left = BstNode(120)
b.right.right.right.right = BstNode(130)
b.right.right.right.left.right = BstNode(140)
b.left.left= BstNode(40)
b.left.right= BstNode(60)
b.left.right.left= BstNode(70)
b.left.right.right= BstNode(80)
b.left.right.right.right= BstNode(90)
b.left.right.right.right.right= BstNode(150)
b.left.right.right.right.right.right= BstNode(160)

root = BstNode(12)
root.left = BstNode(10)
root.right = BstNode(20)
root.right.left = BstNode(25)
root.right.right = BstNode(40)
def See_From_Left(root):
val = []
root.display()
def leftView_util(root, level, Elements_at_levels):
if root is None:
return
if level not in Elements_at_levels:
Elements_at_levels[level] = root.data
leftView_util(root.left, level + 1, Elements_at_levels)
leftView_util(root.right, level + 1, Elements_at_levels)

def leftView(root):
Elements_at_levels = {}
leftView_util(root, 1, Elements_at_levels)
for i in range(1, len(Elements_at_levels) + 1):
val.append(Elements_at_levels[i])

leftView(root)
print(val)

See_From_Left(root)
See_From_Left(b)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sairam Penjarla

Sairam Penjarla

Looking for my next opportunity to make change in a BIG way