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++
#include
using namespace std;
void printSorted(int arr[], int start, int end)
{
if(start > end)
return;
// print left subtree
printSorted(arr, start*2 + 1, end);
// print root
cout << 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;
}
// This code is contributed by Akanksha Rai
[tabby title="C"]
#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; } |
Java
// JAVA Code for Sorted order printing of a // given array that represents a BST class GFG{ private static void printSorted(int[] arr, int start, int end) { if(start > end) return; // print left subtree printSorted(arr, start*2 + 1, end); // print root System.out.print(arr[start] + " "); // print right subtree printSorted(arr, start*2 + 2, end); } // driver program to test above function public static void main(String[] args) { int arr[] = {4, 2, 5, 1, 3}; printSorted(arr, 0, arr.length-1); } } // This code is contributed by Arnav Kr. Mandal. |
Python3
# Python3 Code for Sorted order printing of a # given array that represents a BST def printSorted(arr, start, end): if start > end: return # print left subtree printSorted(arr, start * 2 + 1, end) # print root print(arr[start], end = " ") # print right subtree printSorted(arr, start * 2 + 2, end) # Driver Code if __name__ == '__main__': arr = [4, 2, 5, 1, 3] arr_size = len(arr) printSorted(arr, 0, arr_size - 1) # This code is contributed by PranchalK |
C#
// C# Code for Sorted order printing // of a given array that represents a BST using System; class GFG { static private void printSorted(int []arr, int start, int end) { if(start > end) return; // print left subtree printSorted(arr, start * 2 + 1, end); // print root Console.Write(arr[start] + " "); // print right subtree printSorted(arr, start * 2 + 2, end); } // Driver Code static public void Main(String []args) { int []arr= {4, 2, 5, 1, 3}; printSorted(arr, 0, arr.Length - 1); } } // This code is contributed by Arnab Kundu |
PHP
<?php // PHP Code for Sorted order printing of a // given array that represents a BST function printSorted($arr, $start, $end) { if($start > $end) return; // print left subtree printSorted($arr, $start * 2 + 1, $end); // print root echo($arr[$start] . " "); // print right subtree printSorted($arr, $start * 2 + 2, $end); } // Driver Code $arr = array(4, 2, 5, 1, 3); printSorted($arr, 0, sizeof($arr) - 1); // This code is contributed by Code_Mech. |
Output:
1 2 3 4 5
Time Complexity: O(n)
Please write comments if you find the above solution incorrect, or find better ways to solve the same problem.
leave a comment
0 Comments