Flatten a Binary Search Tree into a Sorted List

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.

Visualization Player

Solution❯

To solve this problem, we need to flatten a Binary Search Tree (BST) into a sorted list. The most efficient way to achieve this is by performing an in-order traversal, which visits nodes in sorted order due to the properties of BSTs.

Case 1: Standard BST

For a typical BST with multiple nodes, an in-order traversal will visit the left subtree, then the current node, and finally the right subtree.

We recursively collect values in this order, which guarantees a sorted list as output.

Case 2: Tree with only left or right children

If the BST has only left children (e.g., a descending linked list), the traversal still works, collecting values from left to right.

If the BST has only right children (e.g., an ascending linked list), the in-order traversal collects values in the same order as they appear.

Case 3: Single-node tree

If the BST consists of just a single node, the sorted list will contain only that node’s value.

This is a valid scenario and should return a list with one element.

Case 4: Empty tree

If the BST is empty (i.e., the root is null), we return an [] — an empty list — since there are no elements to collect.

Approach Summary

We use a recursive in-order traversal approach that:

Traverses the left subtree first
Appends the current node's value
Traverses the right subtree

This approach is efficient and leverages the natural ordering of BSTs.

Algorithm Steps❯

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.

Code

Python

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

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

if __name__ == '__main__':
    # Construct BST:
    #         4
    #        / \
    #       2   6
    #      / \ / \
    #     1  3 5  7
    root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7)))
    print(flattenBST(root))

⬅ Previous TopicFind the kth Smallest Element in a Binary Search Tree

Next Topic ⮕Breadth-First Search in Graphs