Flatten a Binary Search Tree into a Sorted List

Problem and examples

Given a binary search tree (BST), flatten it into a sorted list of values. A BST is a tree data structure where for each node, all nodes in the left subtree have smaller values and all nodes in the right subtree have larger values.

Your task is to return a list of integers representing the values of the BST in ascending order.

This problem is commonly solved using in-order traversal, which naturally visits the nodes in sorted order in a BST.

Input BST	Flattened Sorted List	Description
[5, 3, 7, 2, 4, 6, 8]	[2, 3, 4, 5, 6, 7, 8]	In-order traversal of a balanced BST yields sorted list of values from smallest to largest.
[10, 5, 15, 3, 7, null, 18]	[3, 5, 7, 10, 15, 18]	Standard BST with missing left child under 15. In-order traversal gives correct sorted order.
[1, null, 2, null, 3]	[1, 2, 3]	Right-skewed BST behaves like a sorted linked list. In-order traversal confirms order.
[3, 2, null, 1]	[1, 2, 3]	Left-skewed BST. In-order traversal still results in ascending order.
[42]	[42]	Single-node BST. Flattened result is a single-element list.
[]	[]	Empty BST. The flattened sorted list is also empty.

Explore Flatten a Binary Search Tree into a Sorted List

Load an example or enter your own input. Use the player controls to follow each change.

Understanding the Problem

We are given a Binary Search Tree (BST), and the goal is to flatten it into a sorted list. That means we want to convert the hierarchical structure of the BST into a simple array that contains all the node values in increasing order.

Why does this work well with a BST? Because a BST has a special property: for every node, all values in the left subtree are smaller, and all values in the right subtree are greater. So, if we perform an in-order traversal (Left → Node → Right), we naturally visit the nodes in ascending order.

Step-by-Step Solution with Example

step 1: Choose a suitable traversal

We need a way to visit all nodes in increasing order. The best traversal for this is in-order traversal, which processes the left subtree, then the current node, and then the right subtree.

step 2: Understand how in-order traversal behaves on a BST

Let's take an example BST:


        5
       /       3   7
     /        2   4   9

The in-order traversal for this tree will visit the nodes in this order: 2, 3, 4, 5, 7, 9. This is exactly the sorted order we want.

step 3: Implement a recursive in-order traversal

We'll use a helper function that traverses the tree in in-order fashion and appends each node's value to a result list.

step 4: Combine the results into a single sorted list

After the traversal is complete, the result list will contain all values in sorted order. This becomes our flattened version of the BST.

Edge Cases

Empty Tree

If the BST is null or empty, we simply return an empty list: []. There are no nodes to process.

Single-node Tree

If the tree contains only one node, say 5, then the result list will be [5]. The traversal works correctly even in this minimal case.

Left-skewed Tree

Consider a tree where every node only has a left child, like this:

The in-order traversal would be: 2, 3, 4. Still sorted — no special handling needed.

Right-skewed Tree

For a tree where each node has only a right child:


1
   2
       3

The in-order traversal gives: 1, 2, 3, again correctly sorted.

Finally

Flattening a BST into a sorted list becomes straightforward once we recognize the power of in-order traversal. It leverages the inherent structure of the BST to extract elements in order without any additional sorting steps.

By carefully handling edge cases like empty trees or skewed trees, we ensure the solution is robust and beginner-friendly.

This technique is efficient and commonly used in many coding interviews and real-world systems where sorted access to tree data is required.

If the tree is empty, return an empty list.
Perform an in-order traversal of the binary search tree.
Visit the left subtree, then the current node, and finally the right subtree.
Collect the node values in order; due to BST properties, this will yield a sorted list.
Return the collected list of values.

Implementation and efficiency

C implementation

#include <stdio.h>
#include <stdlib.h>

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorder(struct TreeNode* node) {
    if (node) {
        inorder(node->left);
        printf("%d ", node->val);
        inorder(node->right);
    }
}

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int main() {
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    inorder(root);
    return 0;
}

C++ implementation

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void inorder(TreeNode* node) {
    if (node) {
        inorder(node->left);
        cout << node->val << " ";
        inorder(node->right);
    }
}

int main() {
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(6);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);
    root->right->left = new TreeNode(5);
    root->right->right = new TreeNode(7);

    inorder(root);
    return 0;
}

Python implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def flatten_bst(root):
    result = []
    def inorder(node):
        if node:
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
    inorder(root)
    return result

if __name__ == '__main__':
    root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7)))
    print(flatten_bst(root))

Java implementation

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class FlattenBST {
    public static void inorder(TreeNode node) {
        if (node != null) {
            inorder(node.left);
            System.out.print(node.val + " ");
            inorder(node.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(5);
        root.right.right = new TreeNode(7);

        inorder(root);
    }
}

JavaScript implementation

class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function inorder(node, result) {
    if (node) {
        inorder(node.left, result);
        result.push(node.val);
        inorder(node.right, result);
    }
}

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

const result = [];
inorder(root, result);
console.log(result);

Go implementation

package main

import "fmt"

type TreeNode struct {
    val   int
    left  *TreeNode
    right *TreeNode
}

func inorder(node *TreeNode, result *[]int) {
    if node != nil {
        inorder(node.left, result)
        *result = append(*result, node.val)
        inorder(node.right, result)
    }
}

func main() {
    root := &TreeNode{val: 4}
    root.left = &TreeNode{val: 2}
    root.right = &TreeNode{val: 6}
    root.left.left = &TreeNode{val: 1}
    root.left.right = &TreeNode{val: 3}
    root.right.left = &TreeNode{val: 5}
    root.right.right = &TreeNode{val: 7}

    result := []int{}
    inorder(root, &result)
    fmt.Println(result)
}

Rust implementation

struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

fn inorder(node: &Option<Box<TreeNode>>, result: &mut Vec<i32>) {
    if let Some(n) = node {
        inorder(&n.left, result);
        result.push(n.val);
        inorder(&n.right, result);
    }
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 4,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 1, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 3, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 6,
            left: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 7, left: None, right: None })),
        })),
    }));

    let mut result = Vec::new();
    inorder(&root, &mut result);
    println!("{:?}", result);
}

Kotlin implementation

class TreeNode(var val: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

fun inorder(node: TreeNode?, result: MutableList<Int>) {
    if (node != null) {
        inorder(node.left, result)
        result.add(node.val)
        inorder(node.right, result)
    }
}

fun main() {
    val root = TreeNode(4)
    root.left = TreeNode(2)
    root.right = TreeNode(6)
    root.left?.left = TreeNode(1)
    root.left?.right = TreeNode(3)
    root.right?.left = TreeNode(5)
    root.right?.right = TreeNode(7)

    val result = mutableListOf<Int>()
    inorder(root, result)
    println(result)
}

Swift implementation

class TreeNode {
    var val: Int
    var left: TreeNode?
    var right: TreeNode?
    init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

func inorder(_ node: TreeNode?, _ result: inout [Int]) {
    if let node = node {
        inorder(node.left, &result)
        result.append(node.val)
        inorder(node.right, &result)
    }
}

let root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left?.left = TreeNode(1)
root.left?.right = TreeNode(3)
root.right?.left = TreeNode(5)
root.right?.right = TreeNode(7)

var result: [Int] = []
inorder(root, &result)
print(result)

TypeScript implementation

class TreeNode {
    val: number;
    left: TreeNode | null = null;
    right: TreeNode | null = null;
    constructor(val: number) {
        this.val = val;
    }
}

function inorder(node: TreeNode | null, result: number[]): void {
    if (node) {
        inorder(node.left, result);
        result.push(node.val);
        inorder(node.right, result);
    }
}

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

const result: number[] = [];
inorder(root, result);
console.log(result);