Flatten binary search tree to sorted linked list

Problem

You are given a Binary Search Tree (BST), and the task is to flatten it into a sorted single linked list. The linked list is implemented using the left pointers of the original BST nodes, while the right pointers of all nodes should be set to null.

Examples

Example 1:

graph TD
	4 --- 2 & 5
	2 --- 1 & 3

Input: root = [4,2,5,1,3]
Output: [1,2,3,4,5]
Explanation: The BST nodes are traversed in in-order order to produce the sorted linked list. Each node's left points to the next node in the list, and right is set to null.

Similar Problem

This is very similar to [Convert Binary Search Tree to Sorted Doubly Linked List](convert-binary-search-tree-to-sorted-doubly-linked-list).

Solution

Method 1 - Using in-order traversal

A BST's in-order traversal visits nodes in sorted order. By performing an in-order traversal, we can access the nodes in ascending order.

As we traverse, we can rewire:

• left pointer of the current node to point to the previously visited node.
• right pointer of the current node to be null.

While traversing, maintain a reference to the previous node. Update its left pointer to point to the current node to build the linked list.

Approach

1. Conduct in-order traversal to visit nodes in sorted order.
2. Use a reference to the current head of the linked list and prev node as you build the linked list.
3. For each node:
   • Assign its left pointer to the previously visited node (building the list).
   • Set its right pointer to NULL.
4. Return the head of the flattened linked list.

Code

Java

class Solution {
    private TreeNode prev = null; // Keeps track of the previous node
    private TreeNode head = null; // Head of the linked list

    public TreeNode flattenBST(TreeNode root) {
        // Perform in-order traversal on the BST
        inOrder(root);
        return head;
    }

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

        // Traverse the left subtree
        inOrder(node.left);

        // Process the current node
        if (prev == null) {
            head = node; // If there's no previous node, establish head
        } else {
            prev.left = node; // Rewire `left` pointer of prev node
        }
        node.right = null; // Set the current node's right pointer to null
        prev = node;       // Update prev to be the current node

        // Traverse the right subtree
        inOrder(node.right);
    }
}

Python

class Solution:
    def __init__(self):
        self.prev = None # Keeps track of the previous node
        self.head = None # Head of the linked list

    def flattenBST(self, root):
        # Perform in-order traversal on the BST
        self.inOrder(root)
        return self.head

    def inOrder(self, node):
        if not node:
            return

        # Traverse the left subtree
        self.inOrder(node.left)

        # Process the current node
        if not self.prev:
            self.head = node # If there's no previous node, establish head
        else:
            self.prev.left = node # Rewire `left` pointer of prev node
        node.right = None # Set the current node's right pointer to null
        self.prev = node  # Update prev to be the current node

        # Traverse the right subtree
        self.inOrder(node.right)

Complexity

• ⏰ Time complexity: O(n). The in-order traversal visits every node in the BST exactly once.
• 🧺 Space complexity: O(h). Where h is the height of the BST. Recursive stack space for an in-order traversal equals the height of the tree.