LeetCode 958 - Check Completeness of a Binary Tree

Related: Check if a Binary Tree is Complete Binary Tree
https://leetcode.com/problems/check-completeness-of-a-binary-tree/

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

 

Note:

1. The tree will have between 1 and 100 nodes.

https://leetcode.com/articles/check-completeness-of-a-binary-tree/

题解[1]的做法不错：直接判断按照一个堆的形态来组织树，能否得到一个中间没有空隙的数组。不需要把数组真的建出来，只要给每个结点分配一个index，然后判断index总数是否和结点总数相同就行了。

At the root node, we will associate it with the code 1. Then, for each node with code v, we will associate its left child with code 2 * v, and its right child with code 2 * v + 1.

We can find the codes of every node in the tree in "reading order" (top to bottom, left to right) sequence using a breadth first search. (We could also use a depth first search and sort the codes later.)

Then, we check that the codes are the sequence 1, 2, 3, ... with no gaps. Actually, we only need to check that the last code is correct, since the last code is the largest value.

  public boolean isCompleteTree(TreeNode root) {

    List<ANode> nodes = new ArrayList();

    nodes.add(new ANode(root, 1));

    int i = 0;

    while (i < nodes.size()) {

      ANode anode = nodes.get(i++);

      if (anode.node != null) {

        nodes.add(new ANode(anode.node.left, anode.code * 2));

        nodes.add(new ANode(anode.node.right, anode.code * 2 + 1));

      }

    }

    return nodes.get(i - 1).code == nodes.size();

  }

}

class ANode { // Annotated Node

  TreeNode node;

  int code;

  ANode(TreeNode node, int code) {

    this.node = node;

    this.code = code;

  }

}

X. https://leetcode.com/problems/check-completeness-of-a-binary-tree/discuss/205682/JavaC%2B%2BPython-BFS-Level-Order-Traversal

Use BFS to do a level order traversal,
add childrens to the bfs queue,
until we met the first empty node.

For a complete binary tree,
there should not be any node after we met an empty one.

    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> bfs = new LinkedList<TreeNode>();
        bfs.offer(root);
        while (bfs.peek() != null) {
            TreeNode node = bfs.poll();
            bfs.offer(node.left);
            bfs.offer(node.right);
        }
        while (!bfs.isEmpty() && bfs.peek() == null)
            bfs.poll();
        return bfs.isEmpty();
    }

you may want to return earlier.
We can stop the first while loop when met the first null child.
For then on there should not be any more child.
This optimisation help reduce half of operations.

    public boolean isCompleteTree(TreeNode root) {
        Queue<TreeNode> bfs = new LinkedList<TreeNode>();
        bfs.offer(root);
        while (true) {
            TreeNode node = bfs.poll();
            if (node.left == null) {
                if (node.right != null)
                    return false;
                break;
            }
            bfs.offer(node.left);
            if (node.right == null) break;
            bfs.offer(node.right);
        }
        while (!bfs.isEmpty()) {
            TreeNode node = bfs.poll();
            if (node.left != null || node.right != null)
                return false;
        }
        return true;
    }

X.
https://blog.csdn.net/u013383813/article/details/85032561

将该结点的左右子树 都放入队列中。其实是为了 模拟 满二叉树。
若遍历到某个结点为null，说明这个应该是 完全二叉树的结尾，其后面应该没有结点了，即 队列后面的元素都应为 null。
若已经遍历到 null，队列后面还有 非 null 结点，则该 树不为 完全二叉树。

https://zxi.mytechroad.com/blog/tree/leetcode-958-check-completeness-of-a-binary-tree/

Level order traversal, if any nodes appears after a missing node then the tree is not a perfect binary tree.

variable name: lastLevel, missing, isFinsihing
https://www.saowen.com/a/bed4cb11dd4f472127b72aa0257162a1c978409506b2c8a4c350f9c5187fabcd

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

https://leetcode.com/problems/check-completeness-of-a-binary-tree/discuss/205768/Java-easy-Level-Order-Traversal-one-while-loop

When level-order traversal in a complete tree, after the last node, all nodes in the queue should be null.
Otherwise, the tree is not complete.

    public boolean isCompleteTree(TreeNode root) {
        boolean end = false; // missing
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if(cur == null) end = true;
            else{
                if(end) return false;
                queue.add(cur.left);
                queue.add(cur.right);
            }
        }
        return true;
    }

https://www.geeksforgeeks.org/check-if-a-given-binary-tree-is-complete-tree-or-not/
- Too complex

    static boolean isCompleteBT(Node root)

    {

        // Base Case: An empty tree is complete Binary Tree

        if(root == null)

            return true;

          

        // Create an empty queue

        Queue<Node> queue =new LinkedList<>();

          

        // Create a flag variable which will be set true

        // when a non full node is seen

        boolean flag = false;

          

        // Do level order traversal using queue.

        queue.add(root);

        while(!queue.isEmpty())

        {

            Node temp_node = queue.remove();

              

            /* Check if left child is present*/

            if(temp_node.left != null)

            {

                 // If we have seen a non full node, and we see a node

                 // with non-empty left child, then the given tree is not

                 // a complete Binary Tree

                if(flag == true)

                    return false;

                  

                 // Enqueue Left Child

                queue.add(temp_node.left);

            }

            // If this a non-full node, set the flag as true

            else

                flag = true;

              

            /* Check if right child is present*/

            if(temp_node.right != null)

            {

                // If we have seen a non full node, and we see a node

                // with non-empty right child, then the given tree is not

                // a complete Binary Tree

                if(flag == true)

                    return false;

                  

                // Enqueue Right Child

                queue.add(temp_node.right);

                  

            }

            // If this a non-full node, set the flag as true

            else 

                flag = true;

        }

         // If we reach here, then the tree is complete Bianry Tree

        return true;

    }

X. https://www.geeksforgeeks.org/check-whether-binary-tree-complete-not-set-2-recursive-

1. Calculate the number of nodes (count) in the binary tree.
2. Start recursion of the binary tree from the root node of the binary tree with index (i) being set as 0 and the number of nodes in the binary (count).
3. If the current node under examination is NULL, then the tree is a complete binary tree. Return true.
4. If index (i) of the current node is greater than or equal to the number of nodes in the binary tree (count) i.e. (i>= count), then the tree is not a complete binary. Return false.
5. Recursively check the left and right sub-trees of the binary tree for same condition. For the left sub-tree use the index as (2*i + 1) while for the right sub-tree use the index as (2*i + 2).

    int countNodes(Node root) 

    {

        if (root == null)

            return (0);

        return (1 + countNodes(root.left) + countNodes(root.right));

    }

   

    /* This function checks if the binary tree is complete or not */

    boolean isComplete(Node root, int index, int number_nodes)

    {

        // An empty tree is complete

        if (root == null)        

           return true;

   

        // If index assigned to current node is more than

        // number of nodes in tree, then tree is not complete

        if (index >= number_nodes)

           return false;

   

        // Recur for left and right subtrees

        return (isComplete(root.left, 2 * index + 1, number_nodes)

            && isComplete(root.right, 2 * index + 2, number_nodes));

   

    }

        int node_count = tree.countNodes(tree.root);

        int index = 0;

           

        if (tree.isComplete(tree.root, index, node_count))

            System.out.print("The binary tree is complete");

X. DFS
https://blog.csdn.net/fuxuemingzhu/article/details/85032299

思路是，除了最后一层之外，其余的层必须都是满二叉树，最后一层左边只能全部是非空叶子节点，如果出现None之后，后面不能再有非空叶子节点了。

    def isCompleteTree(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root: return True
        res = []
        self.getlevel(res, 0, root)
        depth = len(res) - 1
        for d in range(depth):
            if d != depth - 1:
                if None in res[d] or len(res[d]) != (2 ** d):
                    return False
            else:
                ni = -1
                for i, n in enumerate(res[d]):
                    if n == None:
                        if ni == -1:
                            ni = i
                    else:
                        if ni != -1:
                            return False
        return True
               

    def getlevel(self, res, level, root):
        if level >= len(res):
            res.append([])
        if not root:
            res[level].append(None)
        else:
            res[level].append(root.val)
            self.getlevel(res, level + 1, root.left)
            self.getlevel(res, level + 1, root.right)


Check whether a binary tree is a full binary tree or not
https://www.geeksforgeeks.org/check-whether-binary-tree-full-binary-tree-not-iterative-approach/

Given a binary tree containing n nodes. The problem is to check whether the given binary tree is a full binary tree or not. A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Conversely, there is no node in a full binary tree, which has only one child node.

Examples:

Input : 
           1
         /   \
        2     3
       / \  
      4   5
Output : Yes

Input :
           1
         /   \
        2     3
       /  
      4   
Output :No

Perform iterative level order traversal of the tree using queue. For each node encountered, follow the steps given below:

1. If (node->left == NULL && node->right == NULL), it is a leaf node. Discard it and start processing the next node from the queue.
2. If (node->left == NULL || node->right == NULL), then it means that only child of node is present. Return false as the binary tree is not a full binary tree.
3. Else, push the left and right child’s of the node on to the queue.

static boolean isFullBinaryTree(Node root) 

{ 

    // if tree is empty 

    if (root != null) 

        return true; 

  

    // queue used for level oder traversal 

    Queue<Node> q = new LinkedList<Node> (); 

  

    // push 'root' to 'q' 

    q.add(root); 

  

    // traverse all the nodes of the binary tree 

    // level by level until queue is empty 

    while (!q.isEmpty()) { 

        // get the pointer to 'node' at front 

        // of queue 

        Node node = q.peek(); 

        q.remove(); 

  

        // if it is a leaf node then continue 

        if (node.left == null && node.right == null) 

            continue; 

  

        // if either of the child is not null and the 

        // other one is null, then binary tree is not 

        // a full binary tee 

        if (node.left == null || node.right == null) 

            return false; 

  

        // push left and right childs of 'node' 

        // on to the queue 'q' 

        q.add(node.left); 

        q.add(node.right); 

    } 

  

    // binary tree is a full binary tee 

    return true; 

} 

https://www.geeksforgeeks.org/check-whether-binary-tree-full-binary-tree-not/

    boolean isFullTree(Node node)

    {

        // if empty tree

        if(node == null)

        return true;

           

        // if leaf node

        if(node.left == null && node.right == null )

            return true;

           

        // if both left and right subtrees are not null

        // the are full

        if((node.left!=null) && (node.right!=null))

            return (isFullTree(node.left) && isFullTree(node.right));

           

        // if none work

        return false;

    }

Related: http://www.ritambhara.in/check-if-a-binary-tree-is-complete-binary-tree/