Fast finding the number of nodes in a complete binary tree

author ：Grey

Original address ： Quickly find the number of nodes of a complete binary tree

Topic link

LeetCode 222. The number of nodes in a complete binary tree

Title Advanced requirements

** Advanced ：** Traversing the tree to count nodes is a method with time complexity of O(n) A simple solution . Can you design a faster algorithm ？

Violence solution

This property of complete binary tree is not considered , Traverse the binary tree directly , Collect the number of nodes of the left and right subtrees , Then add the header node , Is the number of nodes in the complete binary tree , The complete code is as follows

    public static int countNodes1(TreeNode head) {
    
        if (head == null) {
    
            return 0;
        }
        return p(head).all;
    }
    public static Info p(TreeNode head) {
    
        if (head == null) {
    
            return new Info(0);
        }
        Info leftInfo = p(head.left);
        Info rightInfo = p(head.right);
        //  Collect the number of left and right subtree nodes plus the head node , Is the number of nodes in the whole tree 
        int all = leftInfo.all + rightInfo.all + 1;
        return new Info(all);
    }

    public static class Info {
    
        public int all;
        public Info(int a) {
    
            all = a;
        }
    }

The time complexity is O(N).

Optimal solution

We need to use the properties of a complete binary tree , First , We know , The height of the tree , depth , The hierarchy has the following relationship ：

For a complete binary tree , The head node slides to the left until the number of layers obtained by the leaf node must be the maximum number of layers of the binary tree , Suppose the value is h.

If the layer number of the leftmost node of the right tree of the binary tree is exactly equal to h, It shows that the left tree of this binary tree must be a full binary tree

If the layer number of the leftmost node of the right tree of the binary tree is not equal to h, The right tree of this binary tree must be a full binary tree

Because the number of nodes in a full binary tree can be calculated from the height of the tree ：

    public static int countNodes(TreeNode head) {
    
        if (head == null) {
    
            return 0;
        }
        int h = maxLenOfLeft(head, 1);
        return count(head, 1, h);
    }

    private static int count(TreeNode head, int level, int h) {
    
        if (level == h) {
    
            return 1;
        }
        if (maxLenOfLeft(head.right, level + 1) == h) {
    
            //  The left tree must be full 
            return (1 << (h - level)) + count(head.right, level + 1, h);
        } else {
    
            //  The right number must be full , Note that the height is  h - level - 1
            return (1 << (h - level - 1)) + count(head.left, level + 1, h);
        }
    }

    public static int maxLenOfLeft(TreeNode root, int level) {
    
        while (root != null) {
    
            root = root.left;
            level++;
        }
        return level - 1;
    }

By the above method , We don't have to traverse the entire binary tree , You can calculate the nodes , The complexity is lower than O(N).

more

Algorithm and data structure notes