My Java Recursive Solution in O(log(n)*log(n)) Time


  • 4
    K

    Below is my Java solution, after inspiration from some of the answers on this forum and working out the problem by hand.

    For those who don't want to look at the code below directly, here's a pointer: Analyze simple 4, 5 and 6 node trees. Covering these three cases covers ALL cases.

    My code is as below:

    public class Solution {
        
        private int totalNodes = 0;
        
        public int countNodes(TreeNode root) {
            if(root == null) return 0;
            totalNodes = 0;
            count(root);
            return totalNodes;
        }
    
        private void count(TreeNode node) {
            if(node.left == null && node.right == null) {
                totalNodes += 1;
                return;
            }
    
            if(height(node.left) == height(node.right)) {
                totalNodes += (1 << height(node.left));
                if(node.right != null) count(node.right);
            } else {
                totalNodes += (1 << height(node.right));
                if(node.left != null) count(node.left);
            }
        }
    
        private int height(TreeNode node) {
            if(node == null) return 0;
            int height = 1;
            TreeNode tmp = node;
            while(tmp != null) {
                tmp = tmp.left;
                height++;
            }
            return height-1;
        }
    }
    

    Two key differences from other answers I've observed on this topic here:

    1. I've used a private variable, to store final counts instead of
      passing around an argument to recursion. I thought this would be
      much cleaner.
    2. I've sped up my computation by using the bit-shift operator <<. As a side note, if you replace this with Math.pow(2, ...), LeetCode OJ throws a "Time limit exceeded" error. :)

    Also, in the beginning of the count() method, you can see the termination condition laid out very simply: If a node is ever reached, where it has no more children, increment totalNodes by 1 and exit.


  • 0

    That's not O(log(n)). It's O(log(n)^2), just like everybody else's.


  • 0
    K

    Is it O(log(n)*log(n)) because at each point, we're halving halves? What is the derivation of the time complexity?


  • 0
    K

    So at step 1, I reject 1/2 of the total elements right away. That means, I have to check N/2 elements only. Then, I have to check (N/2)/2 = N/4 elements and go down 1 more level. I keep doing this till I reach the "discrepancy" node. The maximum I can travel downwards is log(N), since that's the height of a complete binary tree. At each point of time, I'm either going down left subtree, or right subtree.

    Something about the time complexity you suggest tells me that I'm doing a "binary search on a binary search", if that makes sense. But I don't know how to prove it.


  • 0

    You ignore that height costs O(log n).


  • 0
    K

    Correct! Thanks for this note Stefan! Changed my title.


Log in to reply
 

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