💡 Diameter now reflects the longest path through the root connecting nodes 4 or 5 to node 3.
reconstruct
Return final diameter
The recursion completes and the final diameter value 3 is returned as the longest path length in edges.
💡 Returning the diameter after full traversal gives the longest path in the tree.
Line:return diameter
💡 The diameter variable holds the maximum path length found during recursion.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def diameterOfBinaryTree(root):
diameter = 0 # STEP 1: initialize diameter
def height(node):
nonlocal diameter
if not node: # STEP 4 & 7 & 11: base case for null nodes
return 0
left_height = height(node.left) # STEP 2,3,6,10: recurse left
right_height = height(node.right) # STEP 6,10: recurse right
diameter = max(diameter, left_height + right_height) # STEP 5,8,9,12,13: update diameter
return 1 + max(left_height, right_height) # STEP 5,8,9,12,13: return height
height(root) # STEP 1: start recursion
return diameter # STEP 14: return final diameter
if __name__ == '__main__':
root = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3))
print(diameterOfBinaryTree(root)) # Output: 3
📊
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\w
0
1
i=0
?
?
root node start
Item 1 - wt:0 val:2
i\w
0
1
i=0
?
?
i=1
?
?
left child of root
Item 2 - wt:0 val:4
i\w
0
1
i=0
?
?
i=1
?
?
i=2
?
?
left child of node 2
Item 2 - wt:0 val:4
i\w
0
1
i=0
?
?
i=1
?
?
i=2
0
0
null child height 0
Item 2 - wt:0 val:4
i\w
0
1
i=0
?
?
i=1
?
?
i=2
1
0
height=1
Item 3 - wt:0 val:5
i\w
0
1
i=0
?
?
i=1
?
?
i=2
1
0
i=3
?
?
right child of node 2
Item 3 - wt:0 val:5
i\w
0
1
i=0
?
?
i=1
?
?
i=2
1
0
i=3
0
0
null child height 0
Item 3 - wt:0 val:5
i\w
0
1
i=0
?
?
i=1
?
?
i=2
1
0
i=3
1
0
height=1
Item 1 - wt:0 val:2
i\w
0
1
i=0
?
?
i=1
2
2
i=2
1
0
i=3
1
0
height=2
Item 4 - wt:0 val:3
i\w
0
1
i=0
?
?
i=1
2
2
i=2
1
0
i=3
1
0
i=4
?
?
right child of root
Item 4 - wt:0 val:3
i\w
0
1
i=0
?
?
i=1
2
2
i=2
1
0
i=3
1
0
i=4
0
0
null child height 0
Item 4 - wt:0 val:3
i\w
0
1
i=0
?
?
i=1
2
2
i=2
1
0
i=3
1
0
i=4
1
0
height=1
Item 0 - wt:0 val:1
i\w
0
1
i=0
3
3
i=1
2
2
i=2
1
0
i=3
1
0
i=4
1
0
height=3
Item 0 - wt:0 val:1
i\w
0
1
i=0
3
3
i=1
2
2
i=2
1
0
i=3
1
0
i=4
1
0
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
Step 1: Understand traversal order requirement
The problem requires visiting root before left and right subtrees, which is preorder traversal.
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.
Final Answer:
Option C -> Option C
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
Step 1: Understand the problem constraints
Reconstructing a tree from inorder and postorder requires identifying root nodes and splitting subtrees efficiently.
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.
Final Answer:
Option C -> Option C
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
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.
Step 2: Confirm code logic
The DFS returns True as soon as it finds the matching path sum at a leaf node.
Final Answer:
Option A -> Option A
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
Step 1: Identify auxiliary space usage
The algorithm uses recursion, so space is dominated by recursion stack depth, which is the tree height h.
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.
Final Answer:
Option D -> Option D
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
Step 1: Identify problem with deep recursion
Recursive DFS can cause stack overflow on very deep trees.
Step 2: Use iterative BFS with null markers
Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.
Step 3: Avoid assumptions about uniqueness or balanced shape
Duplicates require storing all nodes explicitly; balanced assumptions break correctness.
Final Answer:
Option A -> Option A
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 unknownstrongwhile earning +1 Grip toward your certificate.