Bird
Raised Fist0
Interview Prepdp-advanced-trees-bitmaskeasyFacebookAmazonGoogle

Diameter of Binary Tree

Choose your preparation mode4 modes available
▶
Steps
setup

Initialize diameter and start recursion at root

The diameter variable is initialized to 0. The recursive height function is called starting at the root node (value 1).

💡 Initializing diameter to zero sets the baseline for updates. Starting at the root begins the bottom-up height calculations.
Line:diameter = 0 height(root)
💡 The algorithm will explore all nodes recursively to compute heights and update diameter.
📊
Diameter of Binary Tree - Watch the Algorithm Execute, Step by Step
Watching the algorithm step through each node's height calculation and diameter update reveals how the longest path is found without redundant computations.
Step 1/14
·Active fill★Answer cell
Item 0 - wt:0 val:1
i\w01
i=0??
root node start
Item 1 - wt:0 val:2
i\w01
i=0??
i=1??
left child of root
Item 2 - wt:0 val:4
i\w01
i=0??
i=1??
i=2??
left child of node 2
Item 2 - wt:0 val:4
i\w01
i=0??
i=1??
i=200
null child height 0
Item 2 - wt:0 val:4
i\w01
i=0??
i=1??
i=210
height=1
Item 3 - wt:0 val:5
i\w01
i=0??
i=1??
i=210
i=3??
right child of node 2
Item 3 - wt:0 val:5
i\w01
i=0??
i=1??
i=210
i=300
null child height 0
Item 3 - wt:0 val:5
i\w01
i=0??
i=1??
i=210
i=310
height=1
Item 1 - wt:0 val:2
i\w01
i=0??
i=122
i=210
i=310
height=2
Item 4 - wt:0 val:3
i\w01
i=0??
i=122
i=210
i=310
i=4??
right child of root
Item 4 - wt:0 val:3
i\w01
i=0??
i=122
i=210
i=310
i=400
null child height 0
Item 4 - wt:0 val:3
i\w01
i=0??
i=122
i=210
i=310
i=410
height=1
Item 0 - wt:0 val:1
i\w01
i=033
i=122
i=210
i=310
i=410
height=3
Item 0 - wt:0 val:1
i\w01
i=033
i=122
i=210
i=310
i=410
final heights and diameter

Key Takeaways

✓ The diameter is computed by combining left and right subtree heights at each node during a single bottom-up traversal.

This insight is hard to see from code alone because the diameter update is embedded inside recursion, but the visualization shows how subtree heights combine.

✓ Height values propagate from leaves up to the root, enabling diameter updates at every node based on subtree heights.

Seeing the monotonic growth of heights clarifies why the recursion returns correct values for diameter calculation.

✓ The longest path (diameter) may pass through the root or any other node, and the algorithm tracks the maximum sum of left and right heights globally.

The visualization shows diameter updates at multiple nodes, illustrating how the maximum path is found anywhere in the tree.

Practice

(1/5)
1. You need to visit all nodes of a binary tree in the order: root node first, then recursively the left subtree, followed by the right subtree. Which algorithmic approach guarantees this traversal order efficiently without extra space for recursion or stack?
easy
A. Postorder traversal using two stacks
B. Level-order traversal using a queue
C. Morris preorder traversal using threaded binary tree
D. Inorder traversal using recursion

Solution

  1. Step 1: Understand traversal order requirement

    The problem requires visiting root before left and right subtrees, which is preorder traversal.
  2. Step 2: Identify approach with no extra space

    Morris preorder traversal uses threaded binary trees to achieve preorder traversal without recursion or stack, thus optimal in space.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Preorder visits root first; Morris traversal achieves this with O(1) space [OK]
Hint: Preorder visits root before children [OK]
Common Mistakes:
  • Confusing inorder or postorder with preorder traversal
  • Assuming recursion is always needed
  • Using level-order which visits nodes by depth
2. You are given two arrays representing the inorder and postorder traversal sequences of a binary tree. Which approach guarantees reconstructing the original tree efficiently without redundant searches?
easy
A. Use a greedy approach by always attaching nodes as left children when possible.
B. Use dynamic programming to store subtrees and avoid recomputation.
C. Use recursion with a hash map to quickly find root indices in the inorder array.
D. Use breadth-first search to reconstruct the tree level by level.

Solution

  1. Step 1: Understand the problem constraints

    Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.
  2. Step 2: Evaluate approaches

    Recursion with a hash map allows O(1) root index lookup in inorder, avoiding repeated linear searches and ensuring O(n) time.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Hash map lookup avoids O(n) search per recursion [OK]
Hint: Hash map lookup avoids repeated linear searches [OK]
Common Mistakes:
  • Assuming greedy or BFS can reconstruct tree uniquely
  • Confusing DP with tree construction
  • Ignoring index lookup cost
3. Consider the following code snippet implementing the optimal DFS approach for the Path Sum problem. Given the tree below and targetSum = 22, what is the return value of the function call hasPathSum(root, 22)? Tree structure: - root = TreeNode(5) - root.left = TreeNode(4) - root.right = TreeNode(8) - root.left.left = TreeNode(11) - root.left.left.left = TreeNode(7) - root.left.left.right = TreeNode(2) - root.right.left = TreeNode(13) - root.right.right = TreeNode(4) - root.right.right.right = TreeNode(1)
def hasPathSum(root: Optional[TreeNode], targetSum: int) -> bool:
    def dfs(node, curr_sum):
        if not node:
            return False
        curr_sum += node.val
        if not node.left and not node.right:
            return curr_sum == targetSum
        return dfs(node.left, curr_sum) or dfs(node.right, curr_sum)
    return dfs(root, 0)
easy
A. True
B. False
C. Raises an exception due to null pointer
D. Returns True only if the root value equals targetSum

Solution

  1. Step 1: Trace the path sums

    Check root-to-leaf paths: - 5↔4↔11↔7 = 27 - 5↔4↔11↔2 = 22 (matches targetSum) - 5↔8↔13 = 26 - 5↔8↔4↔1 = 18 Since one path sums to 22, the function returns True.
  2. Step 2: Confirm code logic

    The DFS returns True as soon as it finds the matching path sum at a leaf node.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Path 5↔4↔11↔2 sums to 22, so return True [OK]
Hint: Check all root-to-leaf paths, not just partial sums [OK]
Common Mistakes:
  • Stopping at non-leaf nodes
  • Ignoring leaf node condition
4. What is the space complexity of the optimal in-place flatten algorithm that uses reverse preorder traversal with a global pointer on a binary tree of n nodes and height h?
medium
A. O(n) due to storing all nodes in a list during traversal
B. O(1) because the algorithm modifies the tree in-place without extra memory
C. O(log n) because the tree height is always balanced and recursion stack is limited
D. O(h) due to recursion stack depth in worst case of skewed tree

Solution

  1. Step 1: Identify auxiliary space usage

    The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.
  2. Step 2: Clarify why O(h) not O(1) or O(n)

    It does not store nodes externally (not O(n)) and is not constant space due to recursion stack (not O(1)). For skewed trees, h can be up to n.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Recursion stack space equals tree height h [OK]
Hint: Recursion stack space equals tree height h [OK]
Common Mistakes:
  • Assuming O(1) space because of in-place modification
  • Confusing recursion stack with explicit data structures
  • Assuming balanced tree always so O(log n) space
5. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?
hard
A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.
B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.
C. Switch to preorder traversal without null markers to reduce string size and recursion depth.
D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

  1. Step 1: Identify problem with deep recursion

    Recursive DFS can cause stack overflow on very deep trees.
  2. Step 2: Use iterative BFS with null markers

    Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.
  3. Step 3: Avoid assumptions about uniqueness or balanced shape

    Duplicates require storing all nodes explicitly; balanced assumptions break correctness.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Iterative BFS with null markers handles deep trees and duplicates safely [OK]
Hint: Iterative BFS avoids recursion limits and preserves structure [OK]
Common Mistakes:
  • Removing null markers to save space breaks reconstruction
  • Using recursion on deep trees causes stack overflow
  • Assuming unique values or balanced trees
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard