To check whether a tree is binary or not

Given a (n-ary) tree. How to check whether it is binary or 开发者_StackOverflow中文版not?

---

How to check whether it is binary or not?

Check if every node has at most 2 children.

Some untested (!) pseudo-code:

struct NTree {

  root: Node

  boolean isBinary() {
    return isBinary(root)
  }

  private boolean isBinary(Node n) {
    if (n has no child)
      return true
    elif (n has 1 child)
      return isBinary(n.children[0])
    elif (n has 2 children)
      return isBinary(n.children[0]) && isBinary(n.children[1])
    else
      return false
  }

  struct Node {
    children: List
  }
}

---

Use any tree traversal algorithm to visit each node, and return false if any node en-route has more than two children.

---

Traverse it and check number of child nodes ≤ 2

---

To avoid using recursion, you can use breadth first traversal.

Queue q <- empty
Enqueue(q, root)
while (q is not empty)
    do u <- Dequeue(q)
       for all u's children
           if they are more than 2, then quit, this is not a binary tree
           else Enqueue(q, all children one by one)
Since we didn't quit in the loop, this is a binary tree