Bird
Raised Fist0
Interview Preptree-dfsmediumAmazonMicrosoftGoogle

Flatten Binary Tree to Linked List

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a complex organizational chart represented as a binary tree, and you want to convert it into a simple linear chain of command without losing the order of hierarchy.

Given the root of a binary tree, flatten the tree into a 'linked list': specifically, the flattened tree should use the right child pointers to point to the next node in a preorder traversal, and all left child pointers should be set to null.

The number of nodes in the tree is in the range [1, 10^5].Node values are unique integers.You must flatten the tree in-place without using extra space for another data structure.
Edge cases: Single node tree → output is the node itself with left=nullTree with only left children → output is a right-skewed linked listTree with only right children → output remains the same
</>
IDE
def flatten(root: Optional[TreeNode]) -> None:public void flatten(TreeNode root)void flatten(TreeNode* root)function flatten(root)
def flatten(root: Optional[TreeNode]) -> None:
    # Write your solution here
    pass
class Solution {
    public void flatten(TreeNode root) {
        // Write your solution here
    }
}
#include <vector>
using namespace std;

void flatten(TreeNode* root) {
    // Write your solution here
}
function flatten(root) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [1, null, 5, null, 6]Greedy approach attaching right subtree before flattening left subtree, losing nodes 2,3,4.✅ Flatten left subtree fully before attaching right subtree; use recursion or stack to preserve preorder.
Wrong: [1, null, 2, null, 3, null, 4, null, 5, null, 6, null, 6]Repeated flattening causing duplication of nodes due to unbounded recursion confusion.✅ Flatten each node exactly once; avoid reusing nodes or duplicating pointers.
Wrong: [1, 2, 3, 4]Not setting left pointers to null, causing incorrect tree structure.✅ Explicitly set node.left = null after rearranging pointers.
Wrong: Runtime error or infinite recursionMissing base case for null root or leaf nodes.✅ Add base case: if root is null, return immediately.
Wrong: Timeout on large inputInefficient O(n^2) approach due to repeated subtree traversals.✅ Use O(n) approach with reverse preorder traversal and a global pointer.
✓
Test Cases
t1_01basic
Input{"root":[1,2,5,3,4,null,6]}
Expected[1,null,2,null,3,null,4,null,5,null,6]

The tree is flattened to a linked list following preorder traversal: 1 -> 2 -> 3 -> 4 -> 5 -> 6, with all left pointers set to null.

t1_02basic
Input{"root":[1,null,2,null,3]}
Expected[1,null,2,null,3]

Tree with only right children remains unchanged after flattening.

t2_01edge
Input{"root":null}
Expectednull

Empty tree input should return null (no nodes to flatten).

t2_02edge
Input{"root":[1]}
Expected[1]

Single node tree remains the same with left set to null.

t2_03edge
Input{"root":[1,2,null,3,null,4,null]}
Expected[1,null,2,null,3,null,4]

Tree with only left children is flattened into a right-skewed linked list.

t3_01corner
Input{"root":[1,2,3,4,5,6,7]}
Expected[1,null,2,null,4,null,5,null,3,null,6,null,7]

Balanced tree flattened in preorder: left subtree fully flattened before right subtree.

t3_02corner
Input{"root":[1,2,null,3,null,4,null,5]}
Expected[1,null,2,null,3,null,4,null,5]

Deep left-skewed tree flattened into right-skewed linked list preserving preorder.

t3_03corner
Input{"root":[1,null,2,null,3,null,4]}
Expected[1,null,2,null,3,null,4]

Right-skewed tree remains unchanged after flattening.

t4_01performance
Input{"root":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}
⏱ Performance - must finish in 2000ms

Large tree with 100 nodes to test O(n) time complexity; must complete within 2 seconds.

Practice

(1/5)
1. You need to output the values of a binary tree's nodes in the order: left subtree, node itself, then right subtree, without modifying the tree structure or using extra space proportional to the tree height. Which approach best fits this requirement?
easy
A. Use a breadth-first search (BFS) to visit nodes level by level.
B. Use a recursive preorder traversal that visits root, left, then right nodes.
C. Use Morris traversal to perform inorder traversal with O(1) extra space by temporarily modifying tree links.
D. Use a dynamic programming approach to store and reuse subtree results.

Solution

  1. Step 1: Understand traversal order requirement

    Inorder traversal visits left subtree, then node, then right subtree, matching the problem's order.
  2. Step 2: Identify approach with O(1) space

    Morris traversal achieves inorder traversal without recursion or stack by temporarily modifying tree pointers, restoring them after use.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Morris traversal is known for O(1) space inorder traversal [OK]
Hint: Morris traversal enables inorder with O(1) space [OK]
Common Mistakes:
  • Confusing preorder with inorder traversal order
  • Assuming BFS can produce inorder sequence
  • Thinking DP applies to traversal order
2. 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
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 time complexity of the optimal iterative postorder traversal algorithm for computing the maximum path sum in a binary tree with n nodes and height h?
medium
A. O(n) because each node is visited a constant number of times
B. O(n log n) due to repeated subtree computations
C. O(h * n) because the stack operations depend on tree height
D. O(n^2) in worst case due to nested traversal of subtrees

Solution

  1. Step 1: Identify node visits

    Each node is pushed and popped from the stack once, and gains are computed once per node.
  2. Step 2: Analyze stack operations and computations

    Stack size is at most h, but operations per node are constant, so total time is proportional to n.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Linear time traversal with constant work per node [OK]
Hint: Each node processed once, O(n) time [OK]
Common Mistakes:
  • Confusing stack height with repeated visits
  • Assuming nested loops cause O(n^2)
  • Thinking recursion stack adds multiplicative factor
5. The following code attempts to compute the diameter of a binary tree using an optimized recursive approach. Identify the line containing the subtle bug that causes incorrect diameter calculation.
medium
A. Line 6: if not node: return 0
B. Line 9: diameter = max(diameter, left + right + 1)
C. Line 10: return 1 + max(left, right)
D. Line 2: diameter = 0

Solution

  1. Step 1: Understand diameter definition counts edges, not nodes.

    The diameter is the number of edges on the longest path, so it should be left + right, not left + right + 1.
  2. Step 2: Identify the bug line.

    Line 9 adds 1 incorrectly, causing diameter to be off by one.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Diameter must be sum of left and right heights (edges), not nodes [OK]
Hint: Diameter counts edges = left + right, not +1 [OK]
Common Mistakes:
  • Adding 1 to diameter sum
  • Not using nonlocal for diameter
  • Returning wrong height value
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