Given an array that stores a complete Binary Search Tree, write a function that efficiently prints the given array in ascending order.
For example, given an array [4, 2, 5, 1, 3], the function should print 1, 2, 3, 4, 5
Solution:
Inorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in standard Inorder Tree Traversal.
Implementation:
[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%20%0Avoid%20printSorted(int%20arr%5B%5D%2C%20int%20start%2C%20int%20end)%0A%7B%20%20%20%20%20%0A%20%20if(start%20%3E%20end)%0A%20%20%20%20return%3B%0A%20%0A%20%20%2F%2F%20print%20left%20subtree%0A%20%20printSorted(arr%2C%20start*2%20%2B%201%2C%20end)%3B%0A%20%0A%20%20%2F%2F%20print%20root%0A%20%20printf(%22%25d%20%20%22%2C%20arr%5Bstart%5D)%3B%0A%20%0A%20%20%2F%2F%20print%20right%20subtree%0A%20%20printSorted(arr%2C%20start*2%20%2B%202%2C%20end)%3B%20%20%0A%7D%0A%20%0Aint%20main()%0A%7B%0A%20%20int%20arr%5B%5D%20%3D%20%7B4%2C%202%2C%205%2C%201%2C%203%7D%3B%0A%20%20int%20arr_size%20%3D%20sizeof(arr)%2Fsizeof(int)%3B%0A%20%20printSorted(arr%2C%200%2C%20arr_size-1)%3B%0A%20%20getchar()%3B%0A%20%20return%200%3B%0A%7D” message=”C Programming” highlight=”” provider=”manual”/]Time Complexity: O(n)
Please write comments if you find the above solution incorrect, or find better ways to solve the same problem.
[ad type=”banner”]