Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
Description taken from https://leetcode.com/problems/maximum-depth-of-binary-tree/.
#Iterative#O(N) Time#O(Log(N)) Space for Balanced Tree, O(N) for Balancedclass Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 stack = [(root, 1)] depth = 1 while stack: node, current_depth = stack.pop() if node is not None: depth = max(depth, current_depth) stack.append((node.left, current_depth+1)) stack.append((node.right, current_depth+1)) return depth#Recursive#O(N) Time#O(Log(N)) Space for Balanced Tree, O(N) for Balancedclass Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right) return max(left_height, right_height) + 1The name of the problem may give a hint that Depth First Search is a good approach to this problem. The reason why a DFS would be better than a Breadth-First Search is that we would have to traverse the entire tree to find the maximum depth with a BFS, but with a DFS, this could be done by only searching a portion of the tree in the average case.
Here we can do a preorder traversal to visit each parent then their left and right child for the iterative version.
We will start by checking if the input root is null, returning a depth of zero if it is.
if root is None: return 0
We will then initialize our stack with the root and a starting depth of one, along with the running depth variable.
stack = [(root, 1)] depth = 1
Next, we will create a loop that will run while there are still nodes in the stack left to process.
while stack:
During each iteration, we will pop a node and its current depth off of the stack.
node, current_depth = stack.pop()
If the node isn't null, we will take the maximum depth between the node's current depth and the running depth we have saved.
if node is not None: depth = max(depth, current_depth)
Afterward, we will append the node's left and right children to the stack, incrementing its current depth by one.
stack.append((node.left, current_depth+1)) stack.append((node.right, current_depth+1))
Once we have traversed the tree through our stack, we will return the max depth we saved.
return depth
We can implement the recursive version with just a few lines of code.
An important distinction between this solution and the iterative one is this solution will have to be a postorder traversal. These are typically done for any recursive tree solution that requires finding the height of a node because, in order for us to know what a node's height is, we will have to know what the height of each node below it is to determine that. Height isn't how far a node is from the root, but how many nodes are under them.
In the iterative solution, we were looking for the maximum depth from the root. Here, we are basically looking for the maximum height which will answer that question as well.
During each recursive call, we will check if the current node is null. If it is, we will return a height of zero for this null node.
if root is None: return 0
If the current call's node is not null, we will recurse the maxDepth function on the left and right children.
At the end of each call, we will return the maximum value between the left and right height, plus one to increment the depth value for nodes that are higher in the recursive call stack.
else: left_height = self.maxDepth(root.left) right_height = self.maxDepth(root.right) return max(left_height, right_height) + 1