Flatten a binary tree into a list of its values using in-order traversal (left, node, right). For a binary search tree this yields the values in sorted order.
flattenTree(root)
Input format: level-order with x for missing children. Output the in-order values
space-separated.
4 2 6 1 3 5 7 // → 1 2 3 4 5 6 7 (a BST flattens to sorted order)
1 x 2 // → 1 2
(empty) // → (empty)
"Flatten a tree into a list" means picking a consistent visiting order, and in-order — left, node, right — is one of the three standard depth-first orderings (pre-order visits the node first, post-order last). The problem specifies in-order explicitly, so the job is implementing that rule faithfully and recursively.
A binary tree is recursive by definition — every child is the root of a smaller tree. So "the in-order list of this tree" is: the in-order list of the left subtree, then this node's value, then the in-order list of the right subtree — a near-literal translation of the definition into a recursive function.
An empty tree contributes nothing — its in-order traversal is an empty sequence. This lets the recursion terminate: nodes with no children have left/right calls that immediately return empty lists.
A BST guarantees every value in a node's left subtree is smaller, every value in its right subtree is larger. In-order visits the whole left subtree (all smaller values) before the node, then the whole right subtree (all larger values) after. Applied recursively at every level, values come out in strictly increasing order — why in-order traversal is the standard way to read a BST back as a sorted sequence.
An iterative version with an explicit stack works too, same O(n) time, but recursion mirrors the tree's own recursive structure with no extra bookkeeping — the call stack does what an explicit stack would otherwise manage manually.
Every node is visited once at O(1) work beyond combining left/right results — O(n) time. Building result lists costs O(n) total space, and recursion depth is bounded by tree height.
def flatten_tree(root):
if root is None:
return []
return flatten_tree(root.left) + [root.val] + flatten_tree(root.right)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.