Print complete Binary Search Tree (BST) in increasing order
Given a level order representation of a complete binary search tree, print its elements in increasing order.
For example, the level order representation of the complete BST below is [15, 10, 20, 8, 12, 18, 25]. The solution should print [8, 10, 12, 15, 18, 20, 25].
1. Recursive Solution
In the array representation of the binary tree, the left child for a node at index i occupies index 2i+1, and the right child occupies index 2i+2. For a complete binary tree, there will be no vacant positions in the array.
The idea is to process the array similarly as an inorder traversal of the binary tree using the above property since our binary tree is a BST – the inorder traversal prints the elements in increasing order.
The algorithm can be implemented as follows in C, Java, and Python:
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <stdio.h> // Recursive function to print a complete binary search tree in increasing order void printIncreasingOrder(int keys[], int low, int high) { if (low > high) { return; } // recur for the left subtree printIncreasingOrder(keys, low*2 + 1, high); // print the root node printf("%d ", keys[low]); // recur for the right subtree printIncreasingOrder(keys, low*2 + 2, high); } int main(void) { int keys[] = { 15, 10, 20, 8, 12, 18, 25 }; int n = sizeof(keys) / sizeof(int); printIncreasingOrder(keys, 0, n - 1); return 0; } |
Output:
8 10 12 15 18 20 25
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Main { // Recursive function to print a complete binary search tree in increasing order public static void printIncreasingOrder(int[] keys, int low, int high) { if (low > high) { return; } // recur for the left subtree printIncreasingOrder(keys, low*2 + 1, high); // print the root node System.out.print(keys[low] + " "); // recur for the right subtree printIncreasingOrder(keys, low*2 + 2, high); } public static void main(String[] args) { int[] keys = { 15, 10, 20, 8, 12, 18, 25 }; printIncreasingOrder(keys, 0, keys.length - 1); } } |
Output:
8 10 12 15 18 20 25
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
# Recursive function to print a complete binary search tree in increasing order def printIncreasingOrder(keys, low, high): if low > high: return # recur for the left subtree printIncreasingOrder(keys, low*2 + 1, high) # print the root node print(keys[low], end=' ') # recur for the right subtree printIncreasingOrder(keys, low*2 + 2, high) if __name__ == '__main__': keys = [15, 10, 20, 8, 12, 18, 25] printIncreasingOrder(keys, 0, len(keys) - 1) |
Output:
8 10 12 15 18 20 25
The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.
2. Iterative Solution
The algorithm can be easily implemented iteratively as well. Following is the iterative version in C++, Java, and Python using an explicit stack:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
#include <iostream> #include <stack> #include <vector> using namespace std; // Iterative function to print a complete binary search tree in increasing order void printIncreasingOrder(vector<int> const &keys) { int n = keys.size(); // base case if (n == 0) { return; } // create a stack to store array indices stack<int> s; // start with the root node (the first array element) int r = 0; // push the root node into the stack s.push(r); // run till stack is empty while (!s.empty()) { // push the left child of the current node into the stack // and repeat the same for the left child while (r == s.top() && r*2 + 1 < n) { r = r*2 + 1; s.push(r); } // print the last processed node and remove it from the stack r = s.top(); s.pop(); cout << keys[r] << ' '; // push the right child of the current node into the stack if (r*2 + 2 < n) { r = r*2 + 2; s.push(r); } } } int main() { vector<int> keys = { 15, 10, 20, 8, 12, 18, 25 }; printIncreasingOrder(keys); return 0; } |
Output:
8 10 12 15 18 20 25
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
import java.util.Stack; class Main { // Iterative function to print a complete binary search tree in increasing order public static void printIncreasingOrder(int[] keys) { // base case if (keys == null || keys.length == 0) { return; } // create a stack to store array indices Stack<Integer> s = new Stack<>(); // start with the root node (the first array element) int r = 0; // push the root node into the stack s.add(r); // run till stack is empty while (!s.isEmpty()) { // push the left child of the current node into the stack // and repeat the same for the left child while (r == s.peek() && r*2 + 1 < keys.length) { r = r*2 + 1; s.add(r); } // print the last processed node and remove it from the stack r = s.pop(); System.out.print(keys[r] + " "); // push the right child of the current node into the stack if (r*2 + 2 < keys.length) { r = r*2 + 2; s.add(r); } } } public static void main(String[] args) { int[] keys = { 15, 10, 20, 8, 12, 18, 25 }; printIncreasingOrder(keys); } } |
Output:
8 10 12 15 18 20 25
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
from collections import deque # Iterative function to print a complete binary search tree in increasing order def printIncreasingOrder(keys): # base case if not keys: return # create a stack to store array indices s = deque() # start with the root node (the first array element) r = 0 # push the root node into the stack s.append(r) # run till stack is empty while s: # push the left child of the current node into the stack # and repeat the same for the left child while r == s[-1] and r*2 + 1 < len(keys): r = r*2 + 1 s.append(r) # print the last processed node and remove it from the stack r = s.pop() print(keys[r], end=' ') # push the right child of the current node into the stack if r*2 + 2 < len(keys): r = r*2 + 2 s.append(r) if __name__ == '__main__': keys = [15, 10, 20, 8, 12, 18, 25] printIncreasingOrder(keys) |
Output:
8 10 12 15 18 20 25
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the size of the BST.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)