C++: Maximum Depth of Binary Tree

Thought Process

To find the maximum depth of a binary tree, we can use a recursive approach. The depth of a tree is the number of edges from the root to the deepest leaf. If the tree is empty ( root == NULL), the depth is 0. Otherwise, the depth is 1 + max(depth of left subtree, depth of right subtree). This approach ensures that we traverse the entire tree and compute the depth efficiently. 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {

        if(root==NULL)
            return 0;

        int leftTree = maxDepth(root->left);
        int rightTree = maxDepth(root->right);

        return 1 + max(leftTree,rightTree);
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each node exactly once, where 'n' is the number of nodes in the tree.

Space Complexity: O(h)

The space used by the recursion stack depends on the height of the tree(h). In the worst case (a skewed tree), the space complexity is O(n).

Code copied!