Flatten a Binary Search Tree into a Sorted List

Binary Search Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

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.

Examples❯

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.

Solution❯

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: 


    4
   /
  3
 /
2

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.

Algorithm Steps❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...