Grokking Tree Coding Patterns for Interviews

0% completed

​

Solution: Maximum Depth (or Height) of Binary Tree

Problem Statement

Given a root node of the binary tree, return the depth (or height) of a binary tree.

The Depth of the binary tree refers to the number of nodes along the longest path from the root node to the farthest leaf node. If the tree is empty, the depth is 0.

Examples

Example 1

  • Input: root = [1, 2, 3, 4, 5]
  • Expected Output: 3
  • Explanation: The longest path is 1->2->4 or 1->2->5 with 3 nodes.

Example 2

  • Input: root = [1, null, 2, null, 3]
  • Expected Output: 3
    • Justification: There's only one path `1->2->3

.....

.....

.....

Like the course? Get enrolled and start learning!
Joseph D

Joseph D

· 2 years ago

As per the definitions in "Introduction to Tree":

  • Height of a Node: The number of edges on the longest path from the node to a leaf.
  • Depth of a Node: The number of edges from the node to the tree's root node.

How come the answers to the problem is simply how many nodes are there in the longest path rather than being the "depth" nor "height"?

L

Lee

· 2 years ago

Calling the space complexity O(h) seems insufficient. Of course it's O(h). That's not interesting.

What's interesting is the space complexity under various scenarios. For the recursive dfs solution, the best case is when the tree is balanced. In this case the space complexity is O(log n).

For this solution, the worst case is when the tree is a linked list (only single children). In this case, the space complexity is O(n).

I feel like the solutions in this course lack appropriate rigor.

Elena Feoktistova

Elena Feoktistova

· 3 years ago

// Definition for a binary tree node.
// class TreeNode {
//     int val;
//     TreeNode left;
//     TreeNode right;
//     TreeNode(int x) { val = x; }
// }

public class Solution {

    public int maxDepth(TreeNode root) {
        if (root == null) { return 0; }
        int maxDepth = 1;
        Stack<NodeWithDepth> stack = new Stack<>();
        stack.push(new NodeWithDepth(1, root));

        while (!stack.isEmpty()) {
            NodeWithDepth curr = stack.pop();
            if (curr.node.left == null && curr.node.right == null) {
                maxDepth = Math.max(curr.depth, maxDepth);
            } else {
                if (curr.node.right != null) {
                    stack.push(new NodeWithDepth(curr.depth + 1, curr.node.right));
                }
                if
Show 1 reply
Pavel Kostenko

Pavel Kostenko

· 2 years ago

For somewone who is new to Binary Trees your inputs doesn't make any sense.

Inputs should be searialized trees in preOrder.

So we can deserialize them in preOrder as well.

You should Either provide more information on how to use your inputs, or do not provide them at all as I believe they are not usefull, if they can not be used as inputs to a solution.

You also may provide a method which builds a tree from your inputs if you believe your inputs are correct and make sense.

First Input:

[1, 2, 3, 4, 5]
// when constructed the tree manually
let root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
console.log('Given tree:');
root.printPre();
root.printIn();
root.printPos
K

kushaan731

· 4 months ago

As someone who isnt fluent in recursion, its kind of difficult