SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

Maximum Depth of a Tree Visualizer

The depth of an empty tree is 0. Otherwise it is 1 plus the deeper of the two subtrees. Each node waits for both children, then reports up.

Start the Maximum Depth of a Tree simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Call maxDepth(50).
  2. Ask the left child 30 for its depth.
  3. Call maxDepth(30).
  4. Ask the left child 20 for its depth.
  5. Call maxDepth(20).
  6. 20 has no left child: that side counts as 0.
  7. 20 has no right child: that side counts as 0.
  8. 20 returns 1 + max(0, 0) = 1.
  9. Left subtree of 30 has depth 1.
  10. Ask the right child 40 for its depth.
  11. Call maxDepth(40).
  12. Ask the left child 35 for its depth.
  13. Call maxDepth(35).
  14. 35 has no left child: that side counts as 0.
  15. 35 has no right child: that side counts as 0.
  16. 35 returns 1 + max(0, 0) = 1.
  17. Left subtree of 40 has depth 1.
  18. 40 has no right child: that side counts as 0.
  19. 40 returns 1 + max(1, 0) = 2.
  20. Right subtree of 30 has depth 2.
  21. … 21 more steps …
  22. 70 returns 1 + max(2, 1) = 3.
  23. Right subtree of 50 has depth 3.
  24. 50 returns 1 + max(3, 3) = 4.
  25. Done. The tree is 4 levels deep.

Try it with your own input →

Maximum depth of a tree in Java, Python, C++, C and JavaScript

int maxDepth(TreeNode node) {
  if (node == null) return 0;
  int left = maxDepth(node.left);
  int right = maxDepth(node.right);
  return 1 + Math.max(left, right);
}
def max_depth(node):
    if node is None:
        return 0
    left = max_depth(node.left)
    right = max_depth(node.right)
    return 1 + max(left, right)
int maxDepth(TreeNode* node) {
  if (!node) return 0;
  int left = maxDepth(node->left);
  int right = maxDepth(node->right);
  return 1 + max(left, right);
}
int maxDepth(struct TreeNode* node) {
  if (node == NULL) return 0;
  int left = maxDepth(node->left);
  int right = maxDepth(node->right);
  return 1 + (left > right ? left : right);
}
function maxDepth(node) {
  if (node === null) return 0;
  const left = maxDepth(node.left);
  const right = maxDepth(node.right);
  return 1 + Math.max(left, right);
}

In an interview

LeetCode 104, Maximum Depth of Binary Tree. The same "ask both children, then combine" shape solves 110 Balanced Binary Tree and 543 Diameter.

Say it as a recurrence first: depth(node) = 1 + max(depth(left), depth(right)). The badge next to each node is the value it returns.

More trees