Grokking Data Structures & Algorithms for Coding Interviews
Vote

0% completed

​

Solution: Maximum Depth (or Height) of Binary Tree

.....

.....

.....

Like the course? Get enrolled and start learning!
A

Anonymous

· 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"?

A

Anonymous

· 3 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.

A

Anonymous

· 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

Reading Progress

0%

Vote for new content