What is the time complexity of recursion approach(Java)?


  • 0
    E

    Well, the recursion approach is pretty simple:

    public int maxDepth(TreeNode root) {  
        if(root == null)  
            return 0;  
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;  
    }  
    

    I just cannot figure out the time complexity of this solution. Somebody says it's O(n). Aren't maxDepth(root.left) and maxDepth(root.right) computed simultaneously, which would make the time complexity O(lgn)? Thanks.


  • -3
    V

    O(logN) on average,

    O(N) on worst case if the tree has only left/right for each level.


  • 0
    A

    I think, the Math.max function cannot return until both left and right are returned, so it basically touches every node.


  • 0
    L

    The complexity is exactly O(n). The recursion would touch every node in the tree, for once. The function wont return until it does so.


  • 0
    U

    The time complexity is O(N) because the recursion traverse each node in the tree


Log in to reply
 

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