if binary tree is full, perfect, complete

full: each node has 0 or 2 child nodes.

// full
    x
 x     x
      x x

// not full
    x
 x     x
x     x x

bool isfull(n):
    if n == null:
        return true
    if n.left == null != n.right == null: // same as ^
        return false
    return (n.left) && (n.right)

perfect: tree has 2^depth -1 nodes (i.e. each level is full).
tip: The depths of left and right subtrees are equal at all levels.

// perfect
    x
 x     x
x x   x x

bool isPerfect(n):
    return depthPerfect(n) != null

int? depthPerfect(n):
    if n == null:
        return 0
    ldepth = (n.left)
    if rdepth == null:
        return null
    rdepth = (n.right)
    if rdepth == null:
        return null
    if ldepth != rdepth:
        return null
    return ldepth +1 // or rdepth +1

complete: nodes at last level are filled from left.
tip: After encountering a null child, no nodes in queue should have any children.

// complete
    x
 x     x
x x   x

// not complete
    x
 x     6
x x     7

    4
 2     6
1     5

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue(node)
    ended = false
    while !q.isEmpty():
        n = q.dequeue()
        if ended && n.left != null:
            return false
        if n.left != null:
            q.enqueue(n.left)
        else:
            ended = true
        if ended && n.right != null:
            return false
        if n.right != null:
            q.enqueue(n.right)
        else:
            ended = true
    return true

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue(node)
    ended = false
    while !q.isEmpty():
        n = q.dequeue()
        if ended && (n.left != null || n.right != null):
            return false        
        if n.left == null && n.right != null:
            return false
        ended = n.left == null || n.right == null
        if n.left != null:
            q.enqueue(n.left)
        if n.right != null:
            q.enqueue(n.right)
    return true

// dfs
bool isComplete(n):
    return (n, count(n) -1)

bool isComplete(n, maxi, i = 0):
    if n == null:
        return true
    if i > maxi:
        return false
    // faster to check right subtree first as
    // right subtree returns false if not complete
    return isComplete(n.right, maxi, i*2 +2)
        && isComplete(n.left, maxi, i*2 +1)

int count(n):
    if n == null:
        return 0
    return 1 + count(n.left) + count(n.right)

// dfs
bool isComplete(n):
    isComplete(n, count: {value: 0}, maxi: {value: 0}, i: 0)
    return count.value < i.value +1

isComplete(n, count, maxi, i):
    if n == null:
        return
    count.value++
    maxi.value = max(maxi.value, i)
    (n.left, count, maxi, i*2 +1)
    (n.right, count, maxi, i*2 +2)

// bfs
bool isComplete(node):
    if node == null:
        return true
    q = new
    q.enqueue((node, iexp: 0))
    i = 0
    while !q.isEmpty():
        n, iexp = q.dequeue()
        if iexp > i:
            return false
        i++
        if n.left != null:
            q.enqueue((n.left, iexp*2 +1))
        if n.right != null:
            q.enqueue((n.right, iexp*2 +2))
    return true

[Hat tip to ctci]