Cracking The Coding Interview Together – Problem 4.9: BST Sequences

We've all built Binary Search Trees (BSTs) by inserting elements one by one. But have you ever paused to consider that a single, unique BST structure can arise from multiple different input sequences? It's a subtle yet profound realization that challenges our intuition about data structure uniqueness. Imagine you're given a perfectly formed BST, and your task is to reverse-engineer its creation: to discover every single array of numbers that, when inserted sequentially, would result in precisely this tree. This isn't just an academic exercise; it forces us to think deeply about permutations, interleaving, and the fundamental properties that define a BST. Today, we're going to tackle this intriguing problem head-on, and by the end, you'll have a robust solution to uncover all possible BST sequences.

Problem Statement

BST Sequences: Given a binary search tree with distinct elements, print all possible arrays that could have led to this tree.

Our mission is clear: given a Binary Search Tree (BST) with distinct elements, we need to generate and print all possible arrays that, when traversed from left to right and each element inserted into an initially empty tree, would yield the exact given BST. We're looking for a comprehensive list of these 'origin' arrays.

Analyze the Problem Together

Let's break this down. First, the constraints: we're dealing with a standard BST, meaning for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. Crucially, all elements are distinct.

Here's the 'Aha!' moment: The root of any BST is always the first element inserted into the tree. Think about it – if it wasn't, some other element would have been inserted first, becoming the root, and then our current 'root' would be a child. This simple fact is our anchor.

Once the root is inserted, all elements destined for its left subtree must be inserted before all elements destined for its right subtree, or vice-versa, or interleaved. The key is that their relative order within their respective subtrees must be preserved. For example, if [1, 2, 3] forms a left subtree, 1 must come before 2, and 2 before 3 among the left subtree elements. But 1 could be inserted, then 5 (from the right subtree), then 2, then 6, then 3.

A naive approach might be to generate all permutations of the tree's elements and then check if each permutation forms the given BST. This is a combinatorial explosion! For N elements, there are N! permutations. Far too inefficient.

Our architectural choice must leverage the BST's recursive nature. We can solve this problem for the root by recursively solving it for its left and right subtrees. The challenge then becomes how to combine the sequences from the left and right subtrees, always remembering to prepend the current node's value.

Questions for the Interviewer

As senior engineers, we always clarify assumptions. Here are a few questions we'd pose:

1. What should be returned if the input BST is empty or null? Should we return an an empty list of lists, or a list containing a single empty list (representing an empty sequence)?
2. The problem states 'distinct elements'. Can we absolutely rely on this, or should our solution be robust to duplicates (which would change BST insertion rules)?
3. What's the maximum number of nodes we expect in the BST? This helps us gauge the practical limits of an exponential solution.
4. What's the desired output format? A List<List<Integer>> is typical, but confirming is always good.

Think About the Solution

Our solution will be inherently recursive, mirroring the structure of the BST itself.

High-Level Architecture:

We'll define a function, let's call it allBSTSequences(TreeNode node), that returns a List<List<Integer>>. Each inner List<Integer> will be one valid sequence.

Base Case:

If node is null (an empty tree), there's only one way to form it: with an empty sequence. So, we return a list containing a single empty list: [[ ]].

Recursive Step:

1. Get Left Sequences: Recursively call allBSTSequences(node.left) to get all possible sequences that form the left subtree. Let's call this leftSequences.
2. Get Right Sequences: Recursively call allBSTSequences(node.right) to get all possible sequences that form the right subtree. Let's call this rightSequences.
3. Weave and Combine: This is the core logic. For every sequence leftSeq in leftSequences and every sequence rightSeq in rightSequences, we need to 'weave' them together. Weaving means combining the two sequences while preserving the relative order of elements within leftSeq and within rightSeq. The current node.val must always be the first element of any resulting sequence.
   • We'll need a helper function, say weaveLists(List<Integer> first, List<Integer> second, List<Integer> prefix, List<List<Integer>> results), to handle this interleaving.
   • This weaveLists function will recursively explore all ways to interleave first and second onto the prefix.
4. Construct Final Result: For each woven sequence generated by weaveLists, we prepend node.val to it and add it to our overall result list.

Edge Cases:

• Single Node Tree: node.left and node.right are null. leftSequences and rightSequences will each contain [[ ]]. The weaveLists will combine these into [[ ]]. Prepending node.val gives [[node.val]]. Correct.
• Skewed Tree (e.g., all left children): One of leftSequences or rightSequences will be [[ ]], simplifying the weaving. The logic should still hold.

The weaveLists function is the most complex part. It will take elements from first or second one by one, adding them to the prefix, and recursively calling itself until both first and second are exhausted. When they are, the prefix represents a complete woven sequence, which is then added to the results list.

Write Code and Explain

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class BSTSequences {

    /**
     * Main function to find all possible arrays that could have led to this BST.
     *
     * @param node The root of the BST.
     * @return A list of lists, where each inner list is a valid sequence.
     */
    public List<List<Integer>> allBSTSequences(TreeNode node) {
        List<List<Integer>> result = new ArrayList<>();

        // Base case: If the node is null, it represents an empty tree.
        // An empty tree can only be formed by an empty sequence.
        if (node == null) {
            result.add(new ArrayList<>()); // Add a list containing an empty list
            return result;
        }

        // Create a prefix for the current node's value.
        // This value will always be the first element in any sequence forming this subtree.
        List<Integer> prefix = new LinkedList<>();
        prefix.add(node.val);

        // Recursively get all sequences for the left and right subtrees.
        List<List<Integer>> leftSequences = allBSTSequences(node.left);
        List<List<Integer>> rightSequences = allBSTSequences(node.right);

        // Weave together each sequence from the left subtree with each sequence from the right subtree.
        // The current node's value (prefix) is prepended to each woven sequence.
        for (List<Integer> left : leftSequences) {
            for (List<Integer> right : rightSequences) {
                List<List<Integer>> woven = new ArrayList<>();
                // The actual weaving happens here.
                // We pass the prefix (current node's value) to be built upon.
                weaveLists(left, right, prefix, woven);
                result.addAll(woven);
            }
        }
        return result;
    }

    /**
     * Helper function to weave two lists together, preserving their internal relative order.
     *
     * @param first The first list of integers.
     * @param second The second list of integers.
     * @param prefix The current sequence built so far (initially contains the root's value).
     * @param results The list to accumulate all woven sequences.
     */
    private void weaveLists(List<Integer> first, List<Integer> second,
                            List<Integer> prefix, List<List<Integer>> results) {
        // Base case: If either list is empty, append the remaining elements of the other list
        // to the prefix and add the complete sequence to results.
        if (first.isEmpty() || second.isEmpty()) {
            List<Integer> currentSequence = new LinkedList<>(prefix);
            currentSequence.addAll(first);   // Add remaining elements from first
            currentSequence.addAll(second);  // Add remaining elements from second
            results.add(currentSequence);
            return;
        }

        // Option 1: Take an element from the 'first' list.
        // Remove the head of 'first', add it to 'prefix', and recurse.
        // Then, backtrack by adding it back to 'first' and removing from 'prefix'.
        int headFirst = first.remove(0);
        prefix.add(headFirst);
        weaveLists(first, second, prefix, results);
        prefix.remove(prefix.size() - 1); // Backtrack: remove from prefix
        first.add(0, headFirst);          // Backtrack: add back to first

        // Option 2: Take an element from the 'second' list.
        // Remove the head of 'second', add it to 'prefix', and recurse.
        // Then, backtrack by adding it back to 'second' and removing from 'prefix'.
        int headSecond = second.remove(0);
        prefix.add(headSecond);
        weaveLists(first, second, prefix, results);
        prefix.remove(prefix.size() - 1); // Backtrack: remove from prefix
        second.add(0, headSecond);        // Backtrack: add back to second
    }

    // Example Usage (for testing purposes, not part of the main solution)
    public static void main(String[] args) {
        // Example BST:
        //      2
        //     / \
        //    1   3
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);

        BSTSequences solver = new BSTSequences();
        List<List<Integer>> sequences = solver.allBSTSequences(root);

        System.out.println("All possible BST sequences:");
        for (List<Integer> seq : sequences) {
            System.out.println(seq);
        }
        // Expected output:
        // [2, 1, 3]
        // [2, 3, 1]

        // Another example:
        //      5
        //     / \
        //    3   7
        //   / \ / \
        //  2  4 6  8
        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(3);
        root2.right = new TreeNode(7);
        root2.left.left = new TreeNode(2);
        root2.left.right = new TreeNode(4);
        root2.right.left = new TreeNode(6);
        root2.right.right = new TreeNode(8);

        List<List<Integer>> sequences2 = solver.allBSTSequences(root2);
        System.out.println("\nAll possible BST sequences for a larger tree:");
        for (List<Integer> seq : sequences2) {
            System.out.println(seq);
        }
        System.out.println("Total sequences: " + sequences2.size()); // Expected: 24
    }
}

Step-by-step Walkthrough:

1. allBSTSequences(TreeNode node):
   • This is our entry point. It initializes an empty result list to store all the final sequences.
   • Base Case: If node is null, it means we've hit an empty subtree. An empty subtree can only be formed by an empty sequence, so we add new ArrayList<>() (an empty list) to result and return it. This is crucial for the recursion to terminate and provide valid "empty" sequences for weaving.
   • Recursive Calls: We recursively call allBSTSequences for node.left and node.right. This gives us leftSequences and rightSequences, which are lists of all possible sequences that could form the respective subtrees without their roots.
   • Weaving: We then iterate through every left sequence in leftSequences and every right sequence in rightSequences. For each pair, we call our weaveLists helper function.
   • Prefixing: Notice that node.val is added to prefix before calling weaveLists. This ensures that the current node's value is always the first element in any sequence generated from this level of recursion, correctly reflecting its role as the root of its subtree.
   • Finally, all the woven sequences (which already have node.val prepended) are added to the main result list.
2. weaveLists(List<Integer> first, List<Integer> second, List<Integer> prefix, List<List<Integer>> results):
   • This is a classic backtracking function designed to interleave two lists.
   • Base Case: If first or second becomes empty, it means we've exhausted all elements from one of the sub-sequences. We then append all remaining elements from the other list to the prefix (which contains the root and elements already chosen from first and second). This complete currentSequence is a valid interleaving, so we add it to results.
   • Recursive Choices (Option 1 - Take from first):
     • We remove(0) the first element from first.
     • We add this element to our prefix.
     • We recursively call weaveLists with the modified first, second, and prefix.
     • Backtracking: After the recursive call returns, we must undo our changes. We remove the last element from prefix and add(0, ...) the element back to first. This restores the lists to their state before this choice, allowing the next option to be explored cleanly.
   • Recursive Choices (Option 2 - Take from second):
     • This is identical to Option 1, but we take an element from second instead.
     • Again, meticulous backtracking is essential to ensure all paths are explored correctly without side effects on subsequent choices.

This combination of recursive calls for subtrees and a backtracking weaveLists function ensures that we explore every valid way to construct the input array while maintaining the BST property (root first, relative order within subtrees preserved).

Time & Space Complexity

Let's dissect the performance characteristics of our solution. This problem inherently involves generating permutations, so we should expect exponential complexity.

Time Complexity:

The most significant contributor to complexity is the weaveLists function. If we have two lists of lengths m and n, the number of ways to interleave them is given by the binomial coefficient (m+n choose m). Each such interleaving involves copying elements, which takes O(m+n) time. So, a single call to weaveLists can take O((m+n choose m) * (m+n)) time.

Now, consider the allBSTSequences function. It makes recursive calls to its left and right children. Let N be the total number of nodes in the BST.

• The number of sequences generated for a tree with N nodes can be very large. For a perfectly balanced tree, it's roughly N! / (product of subtree sizes!).
• At each node, we iterate through leftSequences and rightSequences. If there are S_L left sequences and S_R right sequences, we make S_L * S_R calls to weaveLists.
• The total number of sequences can grow extremely fast. For a balanced tree of height h, the number of sequences can be roughly (N choose N/2) at the root, multiplied by the number of sequences from subtrees.
• In the worst case (e.g., a skewed tree), the number of sequences might be N!.
• Therefore, the overall time complexity is exponential, roughly O(N * N!) or more precisely, O(Sum_over_all_nodes(S_L * S_R * (m+n choose m) * (m+n))), where m and n are the sizes of the left and right child sequences. This is dominated by the number of sequences generated and the cost of weaving them.

Space Complexity:

The space complexity is also exponential. We are storing all generated sequences in memory.

• The depth of the recursion stack for allBSTSequences is O(H) where H is the height of the tree (O(N) in worst case, O(log N) in best case).
• The weaveLists function also uses recursion, adding to the stack space.
• The primary space consumption comes from results list, which stores all List<Integer> sequences. If there are K total sequences, and each sequence has N elements, the space complexity is O(K * N). Since K can be exponential, the space complexity is also exponential, roughly O(N * N!) in the worst case.

Why This Problem Matters (The Senior Perspective)

This problem, while seemingly academic, touches upon several critical concepts that resonate in real-world software engineering:

1. Combinatorial Explosion and Backtracking: It's a prime example of a problem where the number of possible solutions grows exponentially. Understanding when and why this happens is crucial. Our weaveLists function is a classic application of backtracking, a powerful algorithmic paradigm used in scenarios like solving Sudoku, generating permutations, or finding paths in graphs. Recognizing these patterns allows us to apply proven techniques.
2. Recursive Thinking and Divide & Conquer: The entire solution hinges on breaking down the problem into smaller, identical subproblems (left and right subtrees) and then combining their results. This recursive, divide-and-conquer approach is fundamental to designing efficient algorithms for tree and graph structures, from parsing expressions to optimizing database queries.
3. Data Reconstruction Challenges: In real systems, we often deal with data that has been transformed. Reconstructing the original state or understanding all possible paths to a current state is a non-trivial task. Think about version control systems: merging branches is akin to weaving sequences, where the relative order of changes within each branch must be preserved. While not a direct application, the underlying logic of interleaving ordered lists has parallels.
4. Performance Bottlenecks and Scalability: The exponential complexity immediately tells us this solution is not scalable for large BSTs. As senior engineers, we must identify such bottlenecks early. If a business requirement demanded this for massive trees, we'd immediately pivot to discussing approximations, sampling, or alternative data representations, rather than blindly implementing an O(N!) solution. This problem highlights the importance of complexity analysis in architectural decisions.
5. Immutability vs. Mutability in Recursion: Notice how we meticulously add and remove elements in weaveLists to backtrack. This is a common pattern when working with mutable data structures in recursive algorithms. In functional programming paradigms, we might instead pass new, immutable copies of lists, avoiding the explicit backtracking but potentially incurring higher memory allocation costs. Understanding these trade-offs is key to writing robust and performant code.

Final Thoughts

We've embarked on a fascinating journey today, peeling back the layers of a Binary Search Tree to reveal the myriad paths that could have led to its creation. The 'BST Sequences' problem is more than just a coding challenge; it's a masterclass in recursive thinking, backtracking, and understanding the profound implications of combinatorial complexity.

By breaking the problem down, identifying the crucial 'root first' property, and mastering the art of weaving sequences, we've built a robust solution. Remember, the insights gained from problems like this extend far beyond the whiteboard. They sharpen our ability to design, analyze, and troubleshoot complex systems.

Now, I encourage you to ponder: How might this problem change if elements were not distinct? Or if we only needed to find one such sequence? These are the kinds of questions that push us from simply solving problems to truly understanding them.

Happy Coding!