A flattened binary search tree is a modified version of a binary search tree (BST) where all the nodes are arranged in a linear order. In a normal binary search tree, the left and right subtrees of each node are stored separately, which results in a tree-like structure. However, in a flattened binary search tree, all the nodes are arranged in such a way that the left child of each node is the node immediately preceding it in the linear order, and the right child of each node is the node immediately following it in the linear order.
This linear ordering allows for efficient traversal and searching of the tree. In a flattened binary search tree, a binary search can be performed by simply searching for the desired value in the linear array of nodes using standard search algorithms like binary search. This is much faster than performing a traditional binary search on a normal BST, which requires traversing the tree by following the pointers to the left or right subtrees.
The process of flattening a binary search tree involves performing an in-order traversal of the tree and storing the nodes in a linear array in the order in which they are visited. Once the array is constructed, the left and right child pointers of each node are updated to point to the appropriate nodes in the array.
5
/ \
3 7
/ \ / \
1 4 6 8
And here’s what the flattened version of this tree would look like: 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
In the flattened tree, each node is connected to its in-order predecessor (left child) and successor (right child) in the linear order. So, for example, node 5 is connected to nodes 4 and 6 in the flattened tree.
This linear ordering allows us to perform efficient search operations on the tree, as we can simply use standard search algorithms like binary search to search the linear array of nodes. Additionally, the flattened tree takes up less space than the original binary search tree, as there are no separate pointers for left and right child nodes.
class TreeNode(var value: Int, var left: TreeNode? = null, var right: TreeNode? = null)
fun flattenBST(root: TreeNode?): List<TreeNode> {
val result = mutableListOf<TreeNode>()
if (root == null) return result
val stack = mutableListOf<TreeNode>()
var node = root
while (node != null || stack.isNotEmpty()) {
while (node != null) {
stack.add(node)
node = node.left
}
node = stack.removeLast()
result.add(node)
node = node.right
}
for (i in 0 until result.lastIndex) {
result[i].left = null
result[i].right = result[i + 1]
}
result.last().left = null
result.last().right = null
return result
}
fun main() {
val root = TreeNode(5)
root.left = TreeNode(3, TreeNode(1), TreeNode(4))
root.right = TreeNode(7, TreeNode(6), TreeNode(8))
val flattened = flattenBST(root)
for (node in flattened) {
print("${node.value} -> ")
}
println("null")
}This code defines a TreeNode class to represent the nodes of the binary search tree. The flattenBST function takes the root node of a binary search tree as input and returns a list of the flattened nodes.
The function uses a stack-based iterative approach to perform an in-order traversal of the tree. During the traversal, the nodes are added to a result list in the order in which they are visited. Once the traversal is complete, the left and right pointers of each node are updated to point to the appropriate nodes in the linear order.
Note that in this implementation, the left and right pointers of each node are updated to null after the tree has been flattened, since they are no longer needed in the flattened representation.
In this example, we create a binary search tree with the same structure as the example tree I showed earlier. We then call the flattenBST function on the root of the tree to obtain a flattened list of nodes, and print out the values of the nodes in order. The output should be:
1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> null