861020. Flatten BST to sorted list
Flatten BST to sorted list -- 111950
Summary
This problem involves flattening a binary search tree (BST) into a sorted list. The goal is to transform the tree nodes into a linear array, maintaining the original order and uniqueness of the elements.
Detailed Explanation
The provided binary search tree is given in the form of a node structure with values stored in each node. To flatten this tree, we can use an in-order traversal approach, which visits the left child, the current node, and then the right child. This process will allow us to collect all the nodes' values in a sorted manner.
Here's a step-by-step breakdown of the solution:
- Initialize an empty list or array to store the flattened tree.
- Define a recursive function
flattenBSTthat takes the root node as input and performs an in-order traversal:- For each node, recursively traverse its left child, then itself, and finally its right child.
- During the traversal, add each node's value to the list. This is because the in-order traversal order (left-root-right) ensures the values are added in sorted order.
- Once the tree has been fully traversed, return the flattened list.
The time complexity of this approach is O(n), where n is the number of nodes in the tree. The space complexity is O(n), as we need to store all the node values in the output list.
Here's an ASCII art representation of the traversal process:
5
/ \
2 8
/ \ \
1 3 9
The flattened list would be: [1, 2, 3, 5, 8, 9].
Optimized Solutions
Java
public List<Integer> flattenBST(Node root) {
List<Integer> result = new ArrayList<>();
flatten(root, result);
return result;
}
private void flatten(Node node, List<Integer> result) {
if (node == null) return;
flatten(node.left, result);
result.add(node.val);
flatten(node.right, result);
}