Max Depth of a binary tree


  • 0
    S
    class Solution {
    public:
        int maxDepth(TreeNode *root) {
            if(root==NULL) return 0;
            int x=maxDepth(root->left);
            int y=maxDepth(root->right);
            return (x>y?x+1:y+1);
        }
    };

  • 0
    S

    Can any one explain me, what is the space complexity of this program?


  • 0
    S

    This is recursive, so the space complexity is the maximum stack depth. One stack frame is created for each node, but the stack frames do not recreate the entire tree at once, rather, the stack at any particular time represents a path from the root to some current node. The maximum stack depth is the length of the path to the furthest leaf. That length depends on how balanced the tree is - for a balanced tree it is log(n), for an unbalanced tree it is n.


  • 0
    S

    @shad Thanq :)


Log in to reply
 

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