Simple recursive Java solution O(1) space O(n) time


  • 11
    Z
    public void connect(TreeLinkNode root) {
        
        if(root==null) return ;
        
        link(root.left,root.right);
    }
    
    //HELPER FUNCTION TO LINK TWO NODES TOGETHER
    public void link(TreeLinkNode left, TreeLinkNode right){
        
        if(left==null && right==null) return ;
        
        left.next = right;
        link(left.left,left.right);
        link(left.right,right.left);
        link(right.left,right.right);
    }

  • 0
    T

    What about the log(n) calls to link, which means you have 2 * log(n) space used on execution stack, not counting stuff needed for method call.


  • 0

    If so, there is no way to write a space O(n) time algorithm.


  • 0
    T

    @jedihy I'm not sure what you mean by "space O(n) time". My remark is related to zihao_li stating this is O(1) space, when clearly it's O(n) space on a generic tree, and O(log n) on a perfect tree.

    See this algorithm for a true O(1) space O(n) time iterative algorithm which works on any binary tree.


  • 0

    You are right


  • 0
    Z

    Yes, you are right, appreciate for your correction.


  • 0
    F

    I wrote the same code as yours for the first time, but then I realized this was worse than O(n). Let me explain:

                                                  root
                                  /---------------/    \---------------\
                              left                                     right
                      /------/  \------\                        /------/  \------\  
                   subT1             subT2                 subT3                  subT4
    

    Every subTree in the graph has a size of n/4, and the size of the whole tree is n.
    Then, in order to apply the algorithm on the whole problem, the code first apply it on the first two subtrees, then the two subtrees in the middle, and finally the last two. So, if the total time consumption is T(n), then it's formulated as follows:

                                T(n) =  3T(n/2)+O(1)
    

    This results in T(n) being equal to O(n^(ln3/ln2)). As ln3/ln2>ln2/ln2=1, this algorithm is worse than O(n).

    I wrote exactly the same code as yours, but it could not break through 3ms, as many actual O(n) algorithms did. Then I did the analysis above and finally saw why it was coming this way.


  • 0
    H

    @Fanchao true, there are repeated calculation in that code.


Log in to reply
 

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