16. Flatten BST to sorted list
Last updated
Was this helpful?
Last updated
Was this helpful?
The problem can be found at the following link:
To flatten a BST into a sorted list, we can perform an in-order traversal of the BST. During the traversal, we keep track of the previous and next nodes to adjust the pointers accordingly. The steps are as follows:
Initialize head
and tail
pointers as NULL
.
Perform in-order traversal of the BST.
While traversing, adjust the pointers of the nodes to form a linked list.
Finally, return the head of the linked list.
Time Complexity: The time complexity of the in-order traversal is O(n)
, where n is the number of nodes in the BST.
Auxiliary Space Complexity: The space complexity is O(h)
, where h is the height of the BST.
For discussions, questions, or doubts related to this solution, please visit our . We welcome your input and aim to foster a collaborative learning environment.
If you find this solution helpful, consider supporting us by giving a ⭐ star
to the repository.