Flatten a Binary Search Tree into a Sorted List

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.

Flatten a Binary Search Tree into a Sorted List - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

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))