Skip to content

Instantly share code, notes, and snippets.

@SakuraSa

SakuraSa/tree_width.py

Last active October 20, 2015 13:03
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save SakuraSa/d20c7065fd2df5673318 to your computer and use it in GitHub Desktop.
Save SakuraSa/d20c7065fd2df5673318 to your computer and use it in GitHub Desktop.
Download ZIP
get tree width
Raw
tree_width.py
class Node:
left = right = None
def node_only(iterable_nodes):
return filter(bool, iterable_nodes)
def iter_layer(layer):
layer = node_only(layer)
while layer:
yield layer
layer = node_only(node.left for node in layer) + node_only(node.right for node in layer)
def tree_width(root):
return max(map(len, iter_layer([root])) or [0])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment