Thursday, June 23, 2016

if binary tree is full

isfull(n):
    count = {value = 0}
    depth = (n, count)
    return count.value == (1 << depth) -1 // 1 << depth = 2^depth

(n, count):
    if n == null:
        return 0
    count.value++
    return 1 + max((n.left, count), (n.right, count))
[Hat tip to PC]

No comments:

Post a Comment