Start learning free

LESSON 311 OF 347 · BINARY TREES

Flatten Binary Tree in C#: In-Place Reverse Pre-Order DFS

Practice O(n) Read the full explanation

Given the root of a binary tree, flatten the tree into a "linked list":

  • The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
  • The "linked list" should be in the same order as a pre-order traversal of the binary tree.

 

Example 1:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [0]
Output: [0]
STEP 1 OF 10
    Ctrl + Enter to check

    C# · BINARY TREES

    Flatten Binary Tree in C#, explained

    Problem overview

    The method Flatten receives the root of a binary tree and must rewire it in place into a "linked list" that reuses the same TreeNode objects. In the result, every node's left pointer is null and its right pointer points to the next node. The nodes must appear in pre-order: a node first, then its whole left subtree, then its whole right subtree.

    For the tree [1, 2, 5, 3, 4, null, 6], the pre-order is 1, 2, 3, 4, 5, 6, so the flattened chain is 1, 2, 3, 4, 5, 6 linked through right. An empty tree stays empty, and a single node stays as it is. The method returns nothing: the tree itself is changed.

    Approach: build the list from the back

    The natural idea is to collect the pre-order into a list and then relink the nodes. That works, but it needs extra memory. The lesson instead relinks while walking, and it does so by visiting the nodes in the reverse of pre-order: right subtree, then left subtree, then the node itself.

    Walking backwards lets each node link to something that is already finished. Keep a field, lastNode, that always points to the head of the list built so far. When the walk reaches a node, everything that comes after it in pre-order has already been visited, so lastNode is exactly the node that should follow it. The node sets right to lastNode, clears left, and becomes the new head.

    Take the tree above. The reverse order visits 6, 5, 4, 3, 2, 1. Node 6 links to nothing (the list is empty), 5 links to 6, 4 links to 5, 3 links to 4, 2 links to 3 and 1 links to 2. The final chain is 1, 2, 3, 4, 5, 6.

    One thing makes this safe. A node's right and left are read only by the recursive calls, and those calls come before the node overwrites them. By the time a node is rewired, both of its subtrees are already finished.

    Step by step

    1. Add a field lastNode. A field belongs to the object, so every recursive call reads and updates the same variable. A local variable would be separate in each call.
    2. Reset it in Flatten. Fields keep their values between calls, so a second tree must not start with a stale head from the first one.
    3. Call the helper Dfs on the root.
    4. Declare Dfs as a void method that takes a TreeNode. It only rewires nodes.
    5. Base case. A null subtree has nothing to flatten, so return.
    6. Recurse right first. The right subtree comes last in pre-order, so it must be linked before anything that points to it.
    7. Recurse left. After this call, lastNode is the first node of the flattened left subtree, which is what the current node must point to.
    8. Link forward. Set root.right = lastNode.
    9. Clear the left pointer with root.left = null. The left subtree is already in the chain through the right pointers, so nothing is lost.
    10. Become the head. Set lastNode = root so the node processed next will link to this one.

    The solution in C#

    class Solution {
    public void Dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        Dfs(root.right);
        Dfs(root.left);
        root.right = lastNode;
        root.left = null;
        lastNode = root;
    }

    TreeNode lastNode;
    public void Flatten(TreeNode root) {
        lastNode = null;
        Dfs(root);
    }
};

    C# details worth knowing:

    • Field order doesn't matter. Dfs uses lastNode before the line that declares it. In a C# class, members can refer to each other regardless of where they are written.
    • Default value. A field of a reference type such as TreeNode starts as null, and without an access modifier it is private. The explicit reset in Flatten matters only when the same Solution object is used more than once.
    • Reference semantics. root is a reference to a node object. Assigning to root.right changes the node itself, which is why the caller sees the flattened tree even though Flatten returns void. Assigning to the parameter root itself would change only the local copy of the reference.
    • The trailing semicolon. The ; after the class's closing brace is allowed by C# and does nothing.

    Complexity

    Time: O(n). Each node is visited once and does a few assignments.

    Space: O(h), where h is the height of the tree. No new nodes or lists are created. The only extra memory is the recursion stack, which is O(log n) for a balanced tree and O(n) in the worst case, for example a tree that is a single left-leaning chain.

    Edge cases and common mistakes

    • Empty tree. A null root returns at the base case and nothing happens.
    • Single node. Its right is set to null (the reset value of lastNode), its left to null, and it stays alone.
    • Left subtree only. For root 1 with left child 2, node 2 is processed first and then node 1 gets right = 2 and left = null, giving 1, 2.
    • Going left first. If the recursion visited left before right, lastNode would hold the wrong node when the current node links, and the order would not be pre-order.
    • Forgetting root.left = null. The old left pointer would stay and the result would not be a list.
    • Skipping the reset. A reused Solution object would link the last node of the new tree to the old tree's head.
    • Using a local variable instead of a field. Each call would then have its own copy, and the nodes could not find the head of the list built so far.

    Testing

    • [1, 2, 5, 3, 4, null, 6] becomes the chain 1, 2, 3, 4, 5, 6.
    • [] stays empty.
    • [0] stays a single node.
    • A root 1 with only a left child 2 becomes 1, then 2 linked through right.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free