log n

Or n log n

To find the height of a binary tree, you'd have to go over all the nodes. Because you don't know which path would be the longest. So this is O(n). The easiest solution would be doing it recursively, so the it'll be O(log n ) space, for the call stack. But is the tree is unbalansed you might get O(n) worst case. For example if the tree has only one very long branch with only one son to every node. { void* data; treeNode* left; treeNode* right; } int recursiveCalcHeight(treeNode* root) { if(!root) return 0; int leftHeight = recursiveCalcHeight(root->left); int reghtHeight = recursiveCalcHeight(root->right); int max_height = (leftHeight > rightHeight) ? leftHeight : rightHeight; return max_height+1; }

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