1.2 Check if a binary tree is complete

While traversing, cannot meet more nodes after meeting a null

Input: TreeNode root

Output: boolean if the tree is completed

Corner case: if input is null, return true

Data structure: queue

Solution: (Breadth First Research, to deal with logical relation on the same level)

1. Expand one node at a time, use boolean flag to indicate if the node has been expanded

2. Generate its left child, if null, flag = true, not null && not visited, q.offer(),

generate its right child, same as above

TC: n = # of nodes in the tree = O(n)

SC: O(n)

public boolean isComplete(TreeNode root) {
  if (root == null) { return true; }
  Queue<TreeNode> queue = new LinkedList<>();
  boolean flag = false;
  queue.offer(root);
  while (!queue.isEmpty()) {
    TreeNode cur = queue.poll();
    if (cur.left == null) {
       flag = true;
    } else if (flag) {
       return false;
    } else { 	//flag = false && cur.left != null
      queue.offer(root.left);
    }

    if (cur.right == null) {
      flag = true;
    } else if (flag) {
      return false;
    } else { 	//flag = false && cur.right != null
       queue.offer(root.right);
    }
  }
  return true;
}

Same logic and idea could be applied to similar problems such as printing tree level by level when using BreadthFS.

However, record the size of the queue every time first before generating the next level.

Input: TreeNode root

Output: List<List<Integer>> key of each node printed level by level from left to right

public List<List<Integer>> printTree(TreeNode root) {
  List<List<Integer>> res = new ArrayList<>();
  if (root == null) { return res; }
  Queue<TreeNode> queue = new LinkedList<>();
  queue.offer(root);
  while (!queue.isEmpty()) {
    List<Integer> curLevel = new ArrayList<>();
    int size = queue.size();
    for (int i = 0; i < size; i++) {
      TreeNode cur = queue.poll();
      curLevel.add(cur.key);
      if (cur.left != null) {
        queue.offer(cur.left);
      }
      if (cur.right != null) {
         queue.offer(cur.right);
      }
    }
    res.add(curLevel);
  }
  return res;
}