Tree: Height of a Binary Tree

  • + 0 comments

    Python 3, breadth-first traversal, without recursion

    def height(root):
        nodes = {0 : [root]}
        h = 0
        while nodes.get(h):
            nodes[h+1] = []
            for node in nodes[h]:
                if node.left:
                    nodes[h+1].append(node.left)
                if node.right:
                    nodes[h+1].append(node.right)
            h += 1
        return max(nodes.keys()) - 1