BST Sequences in Java
A data structure called a binary search tree makes it easy to maintain a sorted list of numbers up to date.
Since each tree node can only have a maximum of two children, it is known as a binary tree.
Because it can search for a number in O(log(n)) time, it is known as a search tree.
Two characteristics set apart a binary search tree from a standard binary tree:
- Every node in the left subtree is smaller than the root node;
- There are more nodes in the right subtree than there are in the root node
- Each node's two subtrees share the first two characteristics, making them also BSTs.
- A binary search tree (BST) is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree.
We are presented with a binary search tree consisting of individual items. Each element is inserted after moving from left to right along the sequence to build the binary search tree. It is necessary to print every possible combination or method that might generate the specified BST.
Note that the relative order of the items must be maintained when combining the sequences.
Example 1:
Input:
For the given Binary Search Tree,
Output:
The valid BST Sequences for the given input:
[2, 1, 3]
[2, 3, 1]
Approach: Using Merging and Backtracking Concept
Recursively searching the tree, the algorithm returns all possible value sequences that could have resulted in the formation of a given binary search tree (BST). It merges sequences from the left and right subtrees while preserving order at each node by appending the value of the current node as a prefix. To make sure that all valid sequences are produced, backtracking is used for examining each possible combination of insertion orders. Ultimately, it provides a list of every sequence that is acceptable for the BST.
Implementation:
FileName: BSTSequences.java
import java.util.ArrayList;
import java.io.*;
// A binary tree node is represented by this class.
// The generic type T parameter is used to enable the node to store any kind of data.
class TreeNode<T>
{
T data;
TreeNode<T> leftnode, rightnode;
public TreeNode(T data)
{
this.data = data;
this.leftnode = this.rightnode = null;
}
}
public class BSTSequences
{
public static ArrayList<ArrayList<Integer>> BST(TreeNode<Integer> node)
{
ArrayList<ArrayList<Integer>> seq = new ArrayList<>();
// If the node is null, then
// A list with an empty list (indicating an empty sequence) is returned
if (node == null)
{
seq.add(new ArrayList<>());
return seq;
}
// Next, it appends the value of the current node as a prefix
// to each sequence and merges sequences from both
// the right and left subtrees while conserving the order.
ArrayList<Integer> prefix = new ArrayList<>();
prefix.add(node.data);
ArrayList<ArrayList<Integer>> leftSeq = BST(node.leftnode);
ArrayList<ArrayList<Integer>> rightSeq = BST(node.rightnode);
for (ArrayList<Integer> left : leftSeq)
{
for (ArrayList<Integer> right : rightSeq)
{
ArrayList<ArrayList<Integer>> merged = new ArrayList<>();
mergeSequences(left, right, prefix, merged);
seq.addAll(merged);
}
}
return seq;
}
private static void mergeSequences(ArrayList<Integer> left, ArrayList<Integer> right, ArrayList<Integer> prefix, ArrayList<ArrayList<Integer>> merged)
{
// Recursively, it adds the current prefix and preserves the order
// as it merges the left and right sequences.
// To the merged list, it appends the combined sequences.
if (left.isEmpty() && right.isEmpty())
{
merged.add(new ArrayList<>(prefix));
return;
}
// determines whether there are any elements in
// the left sequence that needs to be processed currently.
if (!left.isEmpty())
{
int leftValue = left.remove(0);
prefix.add(leftValue);
mergeSequences(left, right, prefix, merged);
prefix.remove(prefix.size() - 1);
left.add(0, leftValue);
}
// It determines whether the elements are in the right sequence.
if (!right.isEmpty())
{
int rightValue = right.remove(0);
prefix.add(rightValue);
mergeSequences(left, right, prefix, merged);
prefix.remove(prefix.size() - 1);
right.add(0, rightValue);
}
}
public static void main(String[] args)
{
TreeNode<Integer> root = new TreeNode<>(2);
root.leftnode = new TreeNode<>(1);
root.rightnode = new TreeNode<>(3);
// // Invoke the BSTSequence function.
ArrayList<ArrayList<Integer>> seq = BSTSequences.BST(root);
// Printing the sequences
System.out.println("The valid BST Sequences for the given input:");
for (ArrayList<Integer> sequence : seq)
{
System.out.println(sequence);
}
}
}
Output:
The valid BST Sequences for the given input:
[2, 1, 3]
[2, 3, 1]
Complexity Analysis:
The Time complexity for the above code is O(2 ^ N), and the Space complexity is O(N), where 'N' is the number of nodes present in the binary search tree.