Algorithm Binary Search Tree

Sorted order printing of a given array that represents a BST

Sorted order printing of a given array that represents a BST - Binary Search Tree - Given an array that stores a complete Binary Search Tree,

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:

C Programming
#include<stdio.h>
 
void printSorted(int arr[], int start, int end)
{     
  if(start > end)
    return;
 
  // print left subtree
  printSorted(arr, start*2 + 1, end);
 
  // print root
  printf("%d  ", arr[start]);
 
  // print right subtree
  printSorted(arr, start*2 + 2, end);  
}
 
int main()
{
  int arr[] = {4, 2, 5, 1, 3};
  int arr_size = sizeof(arr)/sizeof(int);
  printSorted(arr, 0, arr_size-1);
  getchar();
  return 0;
}

Time Complexity: O(n)

Please write comments if you find the above solution incorrect, or find better ways to solve the same problem.

About the author

Venkatesan Prabu

Wikitechy Founder, Author, International Speaker, and Job Consultant. My role as the CEO of Wikitechy, I help businesses build their next generation digital platforms and help with their product innovation and growth strategy. I'm a frequent speaker at tech conferences and events.

Add Comment

Click here to post a comment