Menu
Yes, it is. Since the elements of the BST satisfy a total preorder, an in-order traversal of the BST must produce those elements in order (Ex: prove it). It is equivalent to state that if we had stored a BST's keys, by an in-order traversal, in an array, the array would be sorted.
The time complexity of that would be O(n + m) where n is the number of nodes and m is the number of edges. Since this is a BST, maximum number of edges would be n - 1 hence the time complexity would be O(n + n - 1) = O(n).
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and less than the ones in its right subtree.
This is not a homework. Just an interesting task :)
Given a complete binary search three represensted by array. Sort the array in O(n) using constant memory.
Example:
Tree:
8
/ \
4 12
/\ / \
2 6 10 14
/\ /\ /\ /\
1 3 5 7 9 11 13 15
Array: 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With