leetcode Question Question: Count Complete Tree Nodes

Count Complete Tree Nodes

Given a complete binary tree, count the number of nodes.

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 2hnodes inclusive at the last level h.

Analysis:

In this problem, directly traverse the binary tree will not pass the OJ. We have to narrow the searching space. Looking at the problem we know that the input binary tree is a complete tree.
It is easier to understand what a complete tree is by drawing some, e.g.,


These are all complete binary trees. Now the problem is how to calculate the nodes as many as possible by computing them rather than counting them one by one.

Firstly we know that, besides the last layer, it is a full tree, which means the number of nodes is computed by \(2^h -1 \), where \(h\) is the depth of tree.

Secondly we have to find out how many node are there in the last layer. It is not difficult to observe that for every leaf node in a complete tree, there is no missing node on its left side.  Consider the last layer of nodes is an array of 0s and 1s and we know the length of the array, e.g. [1,1,1,1...,1,1,0,0,0,...0,0], we want to know how many 1s are there, in an efficient way. What do we have?  Yes, binary search. The basic idea is to locate the middle position of the array and check if it is a 1, if so, search the right half, if not, search the left half, until we find the exact position.

Now it is a little different from the single array, we have a binary tree, but the idea is the same.
Let's see, for the array, we know that the middle position is usually computed by \(st+ (ed-st)/2 \). For the last layer of binary tree, the left-most node in right sub-tree is a good option to represent it!
E.g., for the whole leaf layer, its middle point (left-most node in right sub-tree) is the green dashed node in the figure below, it is an empty node (imagine a 0 in an array [11..100..0]):

In this case, we met an empty node, according to the idea of binary search, we have to search the left half in the same way. Now, where is the middle position?

It's still the left-most node in right sub-tree, but this time the root node is no longer the root node of the whole binary tree, but the left child of the root because we are now dealing with the left part of the tree. (see the blue nodes in the figure above). In this scenario, we find the node, it is not empty, which means, we can easily compute how many leaf nodes are there on the left:  \(2^{h_{sub}-1}\), where \(h_{sub}\) is the depth of the sub-tree (root node in blue color in above figure), -1 is because we only have half of the nodes in last layer.  In this way, we keep the binary searching and finally we can have the number of leaf nodes in this compete tree, the final result is the number of leaf nodes + number of full tree.

Code(C++):

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    // find the depth of left most node in right subtree of current node
    int findSplit(TreeNode* root){
        if (!root || !root->right){
            return 0;
        }else{
            TreeNode* tmp = root->right;
            int dep = 0;
            while (tmp){
                dep += 1;
                tmp = tmp->left;
            }
            return dep;
        }
    }

    int countNodes(TreeNode* root) {
        if (!root){return 0;}
        int res = 0;
        int dep_l = 1;
        int dep_r = 1;
        
        //find left most depth
        TreeNode* tmp = root;
        while (tmp->left){
            dep_l+=1;
            tmp = tmp->left;
        }

        TreeNode* cur_root = root;
        int cur_dep = 1;
        while (cur_dep < dep_l){
            int dep_split = findSplit(cur_root);
            if (dep_split + cur_dep == dep_l){
                cur_root = cur_root->right;
                cur_dep +=1;
                res += pow(2,dep_split-1);
            }else{
                cur_root= cur_root->left;
                cur_dep +=1;
            }
        }
        return pow(2,dep_l-1)+res;
    }
};

Code(Python):

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    
    def findSplitDepth(self, root):
        if not root:
            return 0
        else:
            root = root.right
            dep = 0
            while root:
                root = root.left
                dep += 1
            return dep
    
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if not root:
            return 0
        dep = 1
        tmp = root
        while tmp.left:
            dep += 1
            tmp = tmp.left
        
        cur_root = root
        cur_dep = 1
        res = 0
        while cur_dep < dep:
            dd = self.findSplitDepth(cur_root)
            if dd + cur_dep == dep:
                cur_root = cur_root.right
                res += pow(2, dd-1)
                cur_dep += 1
            else:
                cur_root = cur_root.left
                cur_dep += 1
        
        return pow(2, dep-1) + res