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].
In the array representation of the binary tree, the left child for a node at index i occupies the index 2i+1, and the right child occupies the 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 arr[], int low, int high)
{
if (low > high) {
return;
}
// recur for the left subtree
printIncreasingOrder(arr, low*2 + 1, high);
// print the root node
printf(“%d “, arr[low]);
// recur for the right subtree
printIncreasingOrder(arr, low*2 + 2, high);
}
int main(void)
{
int arr[] = { 15, 10, 20, 8, 12, 18, 25 };
int n = sizeof(arr) / sizeof(int);
printIncreasingOrder(arr, 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[] arr, int low, int high)
{
if (low > high) {
return;
}
// recur for the left subtree
printIncreasingOrder(arr, low*2 + 1, high);
// print the root node
System.out.print(arr[low] + ” “);
// recur for the right subtree
printIncreasingOrder(arr, low*2 + 2, high);
}
public static void main(String[] args)
{
int[] arr = { 15, 10, 20, 8, 12, 18, 25 };
printIncreasingOrder(arr, 0, arr.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
|
# Recursive function to print a complete binary search tree in increasing order
def printIncreasingOrder(arr, low, high):
if low > high:
return
# recur for the left subtree
printIncreasingOrder(arr, low * 2 + 1, high)
# print the root node
print(arr[low], end=‘ ‘)
# recur for the right subtree
printIncreasingOrder(arr, low * 2 + 2, high)
if __name__ == ‘__main__’:
arr = [15, 10, 20, 8, 12, 18, 25]
printIncreasingOrder(arr, 0, len(arr) – 1)
|
Output:
8 10 12 15 18 20 25
Download Run Code
Output:
8 10 12 15 18 20 25
Download Run Code
Output:
8 10 12 15 18 20 25
Download Run Code
Output:
8 10 12 15 18 20 25
The time complexity of the above solution is O(n) and the auxiliary space used by the program is O(n) for call stack.
The algorithm can be easily implemented iteratively as well. Below is the iterative version in C++, Java, and Python using 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
|
#include <iostream>
#include <stack>
using namespace std;
// Iterative function to print a complete binary search tree in increasing order
void printIncreasingOrder(int arr[], int n)
{
// create a stack to store array indices
stack<int> s;
// start with the root node (first element in the array)
int r = 0;
// push root node to the stack
s.push(r);
// run till stack is empty
while (!s.empty())
{
// push the left child of the current node to 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 << arr[r] << ‘ ‘;
// push the right child of the current node to the stack
if (r*2 + 2 < n)
{
r = r*2 + 2;
s.push(r);
}
}
}
int main()
{
int arr[] = { 15, 10, 20, 8, 12, 18, 25 };
int n = sizeof(arr) / sizeof(int);
printIncreasingOrder(arr, n);
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
|
import java.util.Stack;
class Main {
// Iterative function to print a complete binary search tree in increasing order
public static void printIncreasingOrder(int[] arr)
{
// create a stack to store array indices
Stack<Integer> s = new Stack<>();
// start with the root node (first element in the array)
int r = 0;
// push root node to the stack
s.add(r);
// run till stack is empty
while (!s.isEmpty())
{
// push the left child of the current node to the stack
// and repeat the same for the left child
while (r == s.peek() && r*2 + 1 < arr.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(arr[r] + ” “);
// push the right child of the current node to the stack
if (r*2 + 2 < arr.length) {
r = r*2 + 2;
s.add(r);
}
}
}
public static void main(String[] args) {
int[] arr = { 15, 10, 20, 8, 12, 18, 25 };
printIncreasingOrder(arr);
}
}
|
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
|
from collections import deque
# Iterative function to print a complete binary search tree in increasing order
def printIncreasingOrder(arr):
# create a stack to store array indices
s = deque()
# start with the root node (first element in the array)
r = 0
# push root node to the stack
s.append(r)
# run till stack is empty
while s:
# push the left child of the current node to the stack
# and repeat the same for the left child
while r == s[–1] and r * 2 + 1 < len(arr):
r = r * 2 + 1
s.append(r)
# print the last processed node and remove it from the stack
r = s.pop()
print(arr[r], end=‘ ‘)
# push the right child of the current node to the stack
if r * 2 + 2 < len(arr):
r = r * 2 + 2
s.append(r)
if __name__ == ‘__main__’:
arr = [15, 10, 20, 8, 12, 18, 25]
printIncreasingOrder(arr)
|
Output:
8 10 12 15 18 20 25
Download Run Code
Output:
8 10 12 15 18 20 25
Download Run Code
Output:
8 10 12 15 18 20 25
Download Run Code
Output:
8 10 12 15 18 20 25
The time complexity of the above solution is O(n) and the auxiliary space used by the program is O(n) for stack data structure.