# Python solution with detailed explanation

• Solution

Binary Tree Vertical Order Traversal https://leetcode.com/problems/binary-tree-vertical-order-traversal/

Preorder Traversal

• Do a pre-order traversal and maintain two variables to track depth and width. depth is incremented level by level. width increases by 1 when we go right and decreases by 1 when we go left.
• Maintain a dictionary to store preorder values. The key is the width. Value is the sub dictionary with different depths. Pre-order makes sure we get left to right.
``````from pprint import pprint
from collections import defaultdict
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
cache = defaultdict(lambda : defaultdict(list))
self.helper(root, 0, 0, cache)
result = []
for width in sorted(cache.keys()):
result.append([])
for depth in sorted(cache[width].keys()):
for x in cache[width][depth]:
result[-1].append(x)
return result

def helper(self, root, width, depth, cache):
if root == None:
return
cache[width][depth].append(root.val)
self.helper(root.left, width-1, depth+1, cache)
self.helper(root.right, width+1, depth+1, cache)
return
``````

Level Order

• Do a level order traversal. Keep track of width and store in a dictionary.
• level order makes sure top to bottom is maintained. Order of adding children is left to right and that makes sure left to right constraint.
``````from collections import defaultdict, deque
class Solution(object):
def verticalOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
if root == None:
return []
cache = defaultdict(list)
q = deque()
q.append((root, 0))
while len(q):
x,width = q.popleft()
cache[width].append(x.val)
if x.left:
q.append((x.left, width-1))
if x.right:
q.append((x.right, width+1))
result = []
for i in sorted(cache.keys()):
result.append(cache[i])
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.