Skip to content

Instantly share code, notes, and snippets.

/tree_width.py
Created Oct 20, 2015

Embed
What would you like to do?
cal max width of a tree
class Node:
def __init__(self):
self.left = None
self.right = None
def max_width(root):
if not root:
return 0
arr1 = []
arr2 = []
arr1.append(root)
ans = 1
while len(arr1) > 0:
arr2 = []
for node in arr1:
if node.left:
arr2.append(node.left)
if node.right:
arr2.append(node.right)
ans = max(ans, len(arr2))
arr1 = arr2
return ans
n1 = Node()
n2 = Node()
n3 = Node()
n4 = Node()
n5 = Node()
n6 = Node()
n7 = Node()
n8 = Node()
n9 = Node()
n0 = Node()
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n4.right = n6
n5.left = n7
n5.right = n8
n3.right = n9
n3.left = n0
print max_width(n1)
print max_width(n2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.