Bird
Raised Fist0

The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.

medium🐞 Bug Identification Q14 of Q15
Tree: Depth-First Search - Flatten Binary Tree to Linked List
The following code attempts to flatten a binary tree to a linked list in-place. Identify the bug that causes the flattened list to still have left child pointers, violating the problem requirements.
AMissing line to set root.left = None
BLine: flatten(root.left)
CLine: root.right = prev
DLine: flatten(root.right)
Step-by-Step Solution
Solution:

  1. Step 1: Review rewiring steps

    The code sets root.right = prev but does not set root.left = None, so left pointers remain.

  2. Step 2: Identify missing step

    Setting root.left = None is required to ensure the flattened list has no left children.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Left pointers must be nullified to meet problem constraints [OK]
Quick Trick: Always set root.left = None when flattening [OK]
Common Mistakes:
MISTAKES
  • Forgetting to nullify left pointers
  • Misordering recursive calls causing wrong sequence
  • Losing subtree references by incorrect rewiring
Trap Explanation:
PITFALL
  • The code looks almost correct but misses the critical step to nullify left pointers, which is easy to overlook.
Interviewer Note:
CONTEXT
  • Tests attention to detail and understanding of problem constraints on tree transformation.
Master "Flatten Binary Tree to Linked List" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try ItSolutionTrace

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Tree: Depth-First Search Quizzes
Binary Tree Inorder Traversal - Binary Tree Inorder Traversal - Quiz 15hard Binary Tree Postorder Traversal - Binary Tree Postorder Traversal - Quiz 12easy Count Complete Tree Nodes - Count Complete Tree Nodes - Quiz 3easy House Robber III (On Tree) - House Robber III (On Tree) - Quiz 1easy Invert Binary Tree - Invert Binary Tree - Quiz 12easy Lowest Common Ancestor of Binary Tree - Lowest Common Ancestor of Binary Tree - Quiz 14medium Maximum Depth of Binary Tree - Maximum Depth of Binary Tree - Quiz 6medium Path Sum II (All Root-to-Leaf Paths) - Path Sum II (All Root-to-Leaf Paths) - Quiz 5medium Serialize and Deserialize Binary Tree - Serialize and Deserialize Binary Tree - Quiz 8hard Symmetric Tree (DFS Approach) - Symmetric Tree (DFS Approach) - Quiz 6medium