Teaching Kids Programming: Videos on Data Structures and Algorithms
Given the root of a binary tree, return its maximum depth.
A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Recursive Algorithm to Compute the Max Depth of a Binary Tree
If a Tree is None: return 0. Otherwise it will be the maximum of the depth for its left and right tree respectively – which we can recursively call itself to get the value.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 left = self.maxDepth(root.left) right = self.maxDepth(root.right) return max(left, right) + 1 |
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxDepth(self, root: TreeNode) -> int: if root is None: return 0 left = self.maxDepth(root.left) right = self.maxDepth(root.right) return max(left, right) + 1
The time complexity is O(N) where N is the number of the nodes in binary tree. The space complexity is also O(N) due to Recursion.
See also: Teaching Kids Programming – BFS Algorithm to Compute the Maximum Depth of the Binary Tree
Compute the Maximum Depth for a N-ary Tree:
- Teaching Kids Programming – Maximum Depth of N-ary Tree via Depth First Search or Breadth First Search Algorithms
- Teaching Kids Programming – BFS Algorithm to Compute the Maximum Depth of the Binary Tree
- Teaching Kids Programming – Recursive Algorithm to Compute the Maximum Depth of the Binary Tree
- C++ Coding Exercise – Find Maximum Depth of N-ary Tree
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
a WordPress rating system
527 wordsa WordPress rating system
Last Post: Breadth First Search Algorithm to Compute the Sum of a Binary Tree
Next Post: Algorithms to Compute the Sliding Window Product