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);
}
};
Max Depth of a binary tree

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.
