104. Maximum Depth of Binary Tree

📝 Problem Details

• Title: 104. Maximum Depth of a Binary Tree
• Link: https://leetcode.com/problems/maximum-depth-of-binary-tree/
• Difficulty: Easy
• Tags/Categories: Trees DFS

💭What Were My Initial Thoughts?

- implement a DFS solution where you go as deep as possible for a given path in a tree
- record the path's depth
- compre it with a recorded max depth, update max depth if current depth is greater
- do this for every path in the tree

🤔What Did I Struggle With?

1. had a mind blank and started implementing level-order (BFS) traversal for my DFS solution
2. recursive solution was way more simple than what i came up with

💡 Explanation of Solution

in order, do the following:
- recursively search the left subtree of a given root 
- recursively search the right subtree of a given root
	- at this point you should be at a leaf node

- calculate the maxDepth from the bottom of the tree UP, returning the max of the left and right subtrees + the current node you are at

⌛ Complexity Analysis

Time Complexity: O(n) where n is the traversal of n nodes in the tree
Space Complexity:
	- determined by the maximum depth of the recursion stack
	- O(h) where h can be n for a skewed tree (unbalanced)

💻 Implementation of Solution

int maxDepth(TreeNode* root) {
	if(root == nullptr) return 0;
	int leftSubtree =  maxDepth(root->left);
	int rightSubtree = maxDepth(root->right);
	return 1 + max(leftSubtree, rightSubtree);
}