C# - Iterative beats 95% - binary search solution


  • 1

    Always check the height of the left flank of each subtree. If the lengths are equal then the left tree is necessarily full, else the right tree is full. When a tree is full you can count it's nodes using the formula

    2^height - 1
    

    Whichever tree is not full then reset your current node to that subtree and iterate. As an optimization you can skip finding the height of the left subtree on each iteration as this value will be 1 less than the previous height. But the right tree will have to be calculated each iteration. Thus you are only needing to do 1 depth search for each iteration where you are eliminating 1/2 the nodes each time. I believe this is still O(logN * logN) so the solution is the same order as the simpler approach where you check the left and right and recursively but this won't incur the memory usage for the recursion.

        public int CountNodes(TreeNode root) 
        {
            if (root == null) return 0;
            TreeNode node = root;
            int count = 0;
            int leftHeight = LeftHeight(node);
            while (node != null)
            {
                count++; // count self
                int leftLeftHeight = leftHeight - 1;
                int rightLeftHeight = LeftHeight(node.right);
                if (leftLeftHeight == rightLeftHeight)
                {
                    // left tree is full
                    count += (1 << leftLeftHeight) - 1;
                    node = node.right;
                    leftHeight = rightLeftHeight;
                }
                else
                {
                    // right tree is full
                    count += (1 << rightLeftHeight) - 1;
                    node = node.left;
                    leftHeight = leftLeftHeight;
                }
            }
            
            return count;
        }
        
        public int LeftHeight(TreeNode node)
        {
            int count = 0;
            TreeNode n = node;
            while (n != null)
            {
                count++;
                n = n.left;
            }
            return count;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.