Flatten Binary Tree to Linked List

Problem Statement

Flatten a binary tree into a “linked list” where the linked list is represented using the right child pointer of each node and the left child pointer is always null.

What to notice first

• The flattened tree uses only right pointers (like a single-linked list).
• Pre-order traversal order is preserved: root, left subtree, right subtree.
• Left pointers are always set to null in the result.

Examples

Input	Output	Order
[1,2,5,3,4,null,6]	[1,null,2,null,3,null,4,null,5,null,6]	Pre-order: 1→2→3→4→5→6

Constraints

• The number of nodes is in the range [0, 2000].
• -100 <= Node.val <= 100

Real-World Applications

Where this pattern appears

• File system hierarchies and directory structures
• DOM tree manipulation in web browsers
• XML/JSON parsing and configuration management
• Organizational hierarchies and permission trees

Complexity Comparison

Approach	Time	Space	Best When
Pre-Order DFS	O(n)	O(h)	Intuitive; finds rightmost before attaching
Post-Order DFS	O(n)	O(h)	Elegant reverse traversal; track previous

Approach 1: Pre-Order DFS

★ Recommended

Recursively flatten left and right subtrees, then find the rightmost node of the flattened left subtree and attach the right subtree to it.

⏱ Time O(n) Visit each node once 💾 Space O(h) Recursion depth

Pseudocode

function flatten(root):
    if not root: return

    flatten(root.left)
    flatten(root.right)

    if root.left:
        rightmost = root.left
        while rightmost.right:
            rightmost = rightmost.right

        rightmost.right = root.right
        root.right = root.left
        root.left = null

Solution Code

Python

flatten_binary_tree_to_linked_list_preorder_dfs.py

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def flatten(root: Optional[TreeNode]) -> None:
    """
    Flatten binary tree to linked list using pre-order DFS.
    Recursively flattens left and right subtrees, then rewires pointers.
    Time: O(n), Space: O(h) for recursion stack
    """
    if not root:
        return

    flatten(root.left)
    flatten(root.right)

    if root.left:
        # Find the rightmost node in flattened left subtree
        rightmost = root.left
        while rightmost.right:
            rightmost = rightmost.right

        # Attach right subtree to rightmost node
        rightmost.right = root.right
        # Move flattened left subtree to right
        root.right = root.left
        root.left = None


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,5,3,4,null,6]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right = TreeNode(5)
    root.right.right = TreeNode(6)

    flatten(root)
    current = root
    result = []
    while current:
        result.append(current.val)
        current = current.right
    print(f"Example 1: {result}")  # [1, 2, 3, 4, 5, 6]

    # Example 2: Single node
    single = TreeNode(0)
    flatten(single)
    print("Example 2: Single node tree flattened")

C++

flatten_binary_tree_to_linked_list_preorder_dfs.cpp

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void flatten(TreeNode* root) {
        /**
         * Flatten binary tree to linked list using pre-order DFS.
         * Recursively flattens left and right subtrees, then rewires pointers.
         * Time: O(n), Space: O(h) for recursion stack
         */
        if (!root) return;

        flatten(root->left);
        flatten(root->right);

        if (root->left) {
            // Find rightmost node in flattened left subtree
            TreeNode* rightmost = root->left;
            while (rightmost->right) {
                rightmost = rightmost->right;
            }

            // Attach right subtree to rightmost node
            rightmost->right = root->right;
            // Move flattened left subtree to right
            root->right = root->left;
            root->left = nullptr;
        }
    }
};

// Test cases
int main() {
    // Example 1: [1,2,5,3,4,null,6]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    Solution sol;
    sol.flatten(root);

    cout << "Example 1: Tree flattened to linked list using pre-order DFS" << endl;

    return 0;
}

Java

FlattenBinaryTreeToLinkedListPreorderDFS.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    /**
     * Flatten binary tree to linked list using pre-order DFS.
     * Recursively flattens left and right subtrees, then rewires pointers.
     * Time: O(n), Space: O(h) for recursion stack
     */
    public void flatten(TreeNode root) {
        if (root == null) return;

        flatten(root.left);
        flatten(root.right);

        if (root.left != null) {
            // Find rightmost node in flattened left subtree
            TreeNode rightmost = root.left;
            while (rightmost.right != null) {
                rightmost = rightmost.right;
            }

            // Attach right subtree to rightmost node
            rightmost.right = root.right;
            // Move flattened left subtree to right
            root.right = root.left;
            root.left = null;
        }
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: [1,2,5,3,4,null,6]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        Solution sol = new Solution();
        sol.flatten(root);

        System.out.println("Example 1: Tree flattened to linked list using pre-order DFS");
    }
}

JavaScript

flatten_binary_tree_to_linked_list_preorder_dfs.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Flatten binary tree to linked list using pre-order DFS.
 * Recursively flattens left and right subtrees, then rewires pointers.
 * Time: O(n), Space: O(h) for recursion stack
 * @param {TreeNode} root
 * @return {void}
 */
function flatten(root) {
    if (!root) return;

    flatten(root.left);
    flatten(root.right);

    if (root.left) {
        // Find rightmost node in flattened left subtree
        let rightmost = root.left;
        while (rightmost.right) {
            rightmost = rightmost.right;
        }

        // Attach right subtree to rightmost node
        rightmost.right = root.right;
        // Move flattened left subtree to right
        root.right = root.left;
        root.left = null;
    }
}

// Test cases
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right = new TreeNode(5);
root.right.right = new TreeNode(6);

flatten(root);

const result = [];
let current = root;
while (current) {
    result.push(current.val);
    current = current.right;
}
console.log("Example 1:", result);  // [1, 2, 3, 4, 5, 6]

Rust

flatten_binary_tree_to_linked_list_preorder_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Flatten binary tree to linked list using pre-order DFS.
 * Recursively flattens left and right subtrees, then rewires pointers.
 * Time: O(n), Space: O(h) for recursion stack
 */
pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    if let Some(node) = root {
        let mut node_ref = node.borrow_mut();

        let mut left = node_ref.left.take();
        let mut right = node_ref.right.take();

        drop(node_ref);

        flatten(&mut left);
        flatten(&mut right);

        let mut node_ref = node.borrow_mut();

        if let Some(mut l) = left {
            // Find rightmost node in flattened left subtree
            let mut rightmost = l.clone();
            loop {
                let rightmost_ref = rightmost.borrow();
                if rightmost_ref.right.is_none() {
                    break;
                }
                let next = rightmost_ref.right.clone().unwrap();
                drop(rightmost_ref);
                rightmost = next;
            }

            // Attach right subtree to rightmost node
            rightmost.borrow_mut().right = right;
            // Move flattened left subtree to right
            node_ref.right = Some(l);
        } else {
            node_ref.right = right;
        }
    }
}

fn main() {
    println!("Example 1: Tree flattened to linked list using pre-order DFS");
}

Go

flatten_binary_tree_to_linked_list_preorder_dfs.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Flatten binary tree to linked list using pre-order DFS.
 * Recursively flattens left and right subtrees, then rewires pointers.
 * Time: O(n), Space: O(h) for recursion stack
 */
func flatten(root *TreeNode) {
    if root == nil {
        return
    }

    flatten(root.Left)
    flatten(root.Right)

    if root.Left != nil {
        // Find rightmost node in flattened left subtree
        rightmost := root.Left
        for rightmost.Right != nil {
            rightmost = rightmost.Right
        }

        // Attach right subtree to rightmost node
        rightmost.Right = root.Right
        // Move flattened left subtree to right
        root.Right = root.Left
        root.Left = nil
    }
}

func main() {
    fmt.Println("Example 1: Tree flattened to linked list using pre-order DFS")
}

Approach 2: Post-Order DFS with Previous Tracking

optimal

Traverse in post-order (right → left → node), tracking the previous node. Attach previous to current’s right and nullify left.

⏱ Time O(n) Single pass 💾 Space O(h) Recursion depth

Pseudocode

function flatten(root):
    prev = null

    function dfs(node):
        if not node: return

        dfs(node.right)
        dfs(node.left)

        node.right = prev
        node.left = null
        prev = node

    dfs(root)

Solution Code

Python

flatten_binary_tree_to_linked_list_postorder_dfs.py

from typing import Optional


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def flatten(root: Optional[TreeNode]) -> None:
    """
    Flatten binary tree to linked list using post-order DFS with previous tracking.
    Uses a list to track the previous node in-order.
    Time: O(n), Space: O(h) for recursion stack
    """
    prev = [None]

    def dfs(node):
        if not node:
            return

        # Post-order: right, left, then process node
        dfs(node.right)
        dfs(node.left)

        node.right = prev[0]
        node.left = None
        prev[0] = node

    dfs(root)


# Test cases
if __name__ == "__main__":
    # Example 1: [1,2,5,3,4,null,6]
    root = TreeNode(1)
    root.left = TreeNode(2)
    root.left.left = TreeNode(3)
    root.left.right = TreeNode(4)
    root.right = TreeNode(5)
    root.right.right = TreeNode(6)

    flatten(root)
    current = root
    result = []
    while current:
        result.append(current.val)
        current = current.right
    print(f"Example 1: {result}")  # [1, 2, 3, 4, 5, 6]

    # Example 2: Single node
    single = TreeNode(0)
    flatten(single)
    print("Example 2: Single node tree flattened")

C++

flatten_binary_tree_to_linked_list_postorder_dfs.cpp

#include <iostream>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    TreeNode* prev = nullptr;

    void dfs(TreeNode* node) {
        if (!node) return;

        // Post-order: right, left, then process node
        dfs(node->right);
        dfs(node->left);

        node->right = prev;
        node->left = nullptr;
        prev = node;
    }

public:
    void flatten(TreeNode* root) {
        /**
         * Flatten binary tree to linked list using post-order DFS.
         * Uses previous pointer to track last visited node in reverse in-order.
         * Time: O(n), Space: O(h) for recursion stack
         */
        dfs(root);
    }
};

// Test cases
int main() {
    // Example 1: [1,2,5,3,4,null,6]
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->left->left = new TreeNode(3);
    root->left->right = new TreeNode(4);
    root->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    Solution sol;
    sol.flatten(root);

    cout << "Example 1: Tree flattened to linked list using post-order DFS" << endl;

    return 0;
}

Java

FlattenBinaryTreeToLinkedListPostorderDFS.java

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
}

class Solution {
    private TreeNode prev = null;

    private void dfs(TreeNode node) {
        if (node == null) return;

        // Post-order: right, left, then process node
        dfs(node.right);
        dfs(node.left);

        node.right = prev;
        node.left = null;
        prev = node;
    }

    /**
     * Flatten binary tree to linked list using post-order DFS.
     * Uses previous pointer to track last visited node in reverse in-order.
     * Time: O(n), Space: O(h) for recursion stack
     */
    public void flatten(TreeNode root) {
        dfs(root);
    }
}

class Main {
    public static void main(String[] args) {
        // Example 1: [1,2,5,3,4,null,6]
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        Solution sol = new Solution();
        sol.flatten(root);

        System.out.println("Example 1: Tree flattened to linked list using post-order DFS");
    }
}

JavaScript

flatten_binary_tree_to_linked_list_postorder_dfs.js

/**
 * Definition for a binary tree node.
 */
class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

/**
 * Flatten binary tree to linked list using post-order DFS.
 * Uses previous pointer to track last visited node in reverse in-order.
 * Time: O(n), Space: O(h) for recursion stack
 * @param {TreeNode} root
 * @return {void}
 */
function flatten(root) {
    let prev = null;

    function dfs(node) {
        if (!node) return;

        // Post-order: right, left, then process node
        dfs(node.right);
        dfs(node.left);

        node.right = prev;
        node.left = null;
        prev = node;
    }

    dfs(root);
}

// Test cases
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.left.left = new TreeNode(3);
root.left.right = new TreeNode(4);
root.right = new TreeNode(5);
root.right.right = new TreeNode(6);

flatten(root);

const result = [];
let current = root;
while (current) {
    result.push(current.val);
    current = current.right;
}
console.log("Example 1:", result);  // [1, 2, 3, 4, 5, 6]

Rust

flatten_binary_tree_to_linked_list_postorder_dfs.rs

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

/**
 * Flatten binary tree to linked list using post-order DFS.
 * Uses previous pointer to track last visited node in reverse in-order.
 * Time: O(n), Space: O(h) for recursion stack
 */
pub fn flatten(root: &mut Option<Rc<RefCell<TreeNode>>>) {
    let mut prev = None;
    dfs(root, &mut prev);
}

fn dfs(
    node: &mut Option<Rc<RefCell<TreeNode>>>,
    prev: &mut Option<Rc<RefCell<TreeNode>>>,
) {
    if let Some(n) = node.take() {
        let mut n_ref = n.borrow_mut();

        let mut left = n_ref.left.take();
        let mut right = n_ref.right.take();

        drop(n_ref);

        // Post-order: right, left, then process node
        dfs(&mut right, prev);
        dfs(&mut left, prev);

        let mut n_ref = n.borrow_mut();
        n_ref.right = prev.take();
        n_ref.left = None;

        *prev = Some(n);
    }
}

fn main() {
    println!("Example 1: Tree flattened to linked list using post-order DFS");
}

Go

flatten_binary_tree_to_linked_list_postorder_dfs.go

package main

import "fmt"

/**
 * Definition for a binary tree node.
 */
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

/**
 * Flatten binary tree to linked list using post-order DFS.
 * Uses previous pointer to track last visited node in reverse in-order.
 * Time: O(n), Space: O(h) for recursion stack
 */
func flatten(root *TreeNode) {
    var prev *TreeNode
    dfs(root, &prev)
}

func dfs(node *TreeNode, prev **TreeNode) {
    if node == nil {
        return
    }

    // Post-order: right, left, then process node
    dfs(node.Right, prev)
    dfs(node.Left, prev)

    node.Right = *prev
    node.Left = nil
    *prev = node
}

func main() {
    fmt.Println("Example 1: Tree flattened to linked list using post-order DFS")
}

Related Problems

• Path Sum II ↗ Medium #113
• Binary Tree Inorder Traversal ↗ Easy #94
• Binary Tree Preorder Traversal ↗ Easy #144

Interview Tips

Key trade-offs to discuss

• Pre-Order: More intuitive, easier to visualize where to attach subtrees.
• Post-Order: More elegant, single pass with previous tracking; demonstrates understanding of reverse traversal.
• Difference: Pre-order requires finding rightmost; post-order does it implicitly via reverse order.

← Previous
#112 Path Sum Next
#117 Populating Next Right Pointers in Each Node II →