[Solved] Consider the following Python code implementing the optimal flatten function... Given the input tree: 1 / \ 2 3 What is the value of the global variable prev after the call flatten(root) completes? | Tree: Depth-First Search

Tree: Depth-First Search - Flatten Binary Tree to Linked List

Consider the following Python code implementing the optimal flatten function for a binary tree. Given the input tree: 1 / \ 2 3 What is the value of the global variable prev after the call flatten(root) completes?

ATreeNode with val=3

BTreeNode with val=1

CTreeNode with val=2

DNone

Step-by-Step Solution

Solution:

Step 1: Trace flatten calls on root=1
flatten(1) calls flatten(3) then flatten(2). After flatten(3), prev=TreeNode with val=3; after flatten(2), prev=TreeNode with val=2; finally, root=1 sets root.right=prev (2) and prev=TreeNode with val=1.
Step 2: Final value of prev after flatten(1)
After processing root=1, prev points to the root node with val=1.
Final Answer:
Option B -> Option B
Quick Check:
Global prev ends at root node after full traversal [OK]

Quick Trick: Global prev ends at root after full flatten [OK]

Common Mistakes:

MISTAKES

Assuming prev ends at last leaf node
Confusing order of recursive calls
Forgetting prev is updated after rewiring

Trap Explanation:

PITFALL

Candidates often think prev ends at the last visited leaf, but it actually ends at the root after rewiring all nodes.

Interviewer Note:

CONTEXT

Tests candidate's ability to mentally execute recursion and track global state.

Master "Flatten Binary Tree to Linked List" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Tree: Depth-First Search Quizzes

Given the input tree: 1 / \ 2 3 What is the value of the global variable prev after the call flatten(root) completes?

Step 1: Trace flatten calls on root=1

Step 2: Final value of prev after flatten(1)

Final Answer:

Quick Check:

Want More Practice?