A Binary Search Tree is a data structure composed of nodes. These nodes are either null or have references (links) to other nodes. These 'other' nodes are child nodes known as the left and right nodes.

In this article, we will discuss binary search tree data structure in brief, examples, approach, and how to replace every element with the least greater element on its right,its time, and space complexity.

Binary Search tree

A binary search tree (BST) is a binary tree in which each node has a Comparable key (and an associated value) and the key in any node is greater than the keys in all nodes in that node's left subtree and less than the keys in all nodes in that node's right subtree.

Problem statement

Given an array of integers in which we have to replace every element in the array with the least greater element on its right side. If no greater element is on the right side then we have to replace it with -1.

Example

Input

Explanation & Output

In the above example, we are just trying to replace every element with the least greater element on its right

Brute force Approach

ðŸ”ºA simple way is to run two loops. The outer loop will choose an array of elements one by one from left to right. On its right side, the inner loop will look for the smallest element greater than the selected element. Finally, the outer loop will replace the element chosen with the element discovered by the inner loop. This method's time complexity will be O(n^2).

ðŸ”ºUsing Binary Search Trees would be a difficult solution. Starting from the right, we scan the array and insert each element into the BST. In BST, we replace each added element in the array with its in-order successor. If the added element is the maximum so far (i.e. its inorder successor does not exist), it is replaced by -1.

Algorithm

ðŸ”» To solve this problem, we are using the above-mentioned BST approach in which we will create two functions. First will be the constructor in which we will assign the null values, and the second function will be the insertion function which inserts the node with the condition given below.

ðŸ”»The insertion function has two arguments one is to determine the child of the tree and the other is the value.

ðŸ”»We are inserting the node by the following method:

if (node == null)
{
node = new Node(value);
}
// If the key node is smaller than the root's key, go to left subtree and set successors
// as current node
if (value < node.value)
{
successor = node;
node.left = nodeinsertion(node.left, value);
}
else if (value > node.value)
node.right = nodeinsertion(node.right, value);
return node;
}

ðŸ”» Finally, we will print the array with the element which has the least greater element on its right.

Java code

// Java program to Replace every element with the least greater element on its right
import java.io.*;
import java.util.*;
class BinarySearchTree {
class Node {
int value;
Node left, right;
Node(int d) {
value = d;
left = right = null;
}
}
static Node root;
static Node successor;
BinarySearchTree() {
root = null;
successor = null;
}
Node nodeinsertion(Node node, int value) {
if (node == null) {
node = new Node(value);
}
// If the key is smaller than root's key, go to left subtree and set successoressor as current node
if (value < node.value) {
successor = node;
node.left = nodeinsertion(node.left, value);
}
// Go to right subtree
else if (value > node.value)
node.right = nodeinsertion(node.right, value);
return node;
}
// Driver code
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the number of nodes which you want to insert");
int arsize = sc.nextInt();
int arr[] = new int[arsize];
int n = arr.length;
System.out.println("Enter the elements of the array");
for (int i = 0; i < arsize; i++) {
arr[i] = sc.nextInt();
}
System.out.println("\n Tree before replace every element with the least greater element on its right");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
// replacing every element with the least greater element on its right
BinarySearchTree tree = new BinarySearchTree();
// starting from right to left
for (int i = n - 1; i >= 0; i--) {
successor = null;
// nodeInsertioning current element into BST and finding its inorder successoressor
root = tree.nodeinsertion(root, arr[i]);
// Replacing element by its inorder successoressor in BST
if (successor != null)
arr[i] = successor.value;
// No inorder successoressor
else
arr[i] = -1;
}
System.out.println("\n Tree after replace every element with the least greater element on its right");
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}

Output

Complexity analysis

Time complexity

O(N), since we are using a loop to traverse the tree.

Space complexity

O(N), since we are using an array to take the data from the user for each node.

Better Approach

We will be using the Next greater element using the stack algorithm in this approach as it appears to be the better approach to solve the question because it takes O(log(N)) time to execute.

Algorithm

ðŸ”»First, we create an array of pairs called temp and store each element and its index in it.

ðŸ”»Sort the array based on the array elements.

ðŸ”»Now, using Next Greater Element, get the next greater index for every index of the temp array in an array namely index.

ðŸ”»Index[i] now holds the index of next least greater element of the element temp[i].first, and if index[i] is -1, it signifies there is no least greater element of the element temp[i].second on its right side.

ðŸ”»Take a result array where result[i] equals a[indexes[temp[i]] .second]] if index[i] is not -1; otherwise, result[i] is -1.

Java Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;
import java.util.Stack;
import java.util.*;
import java.io.*;
public class Codingninjas {
// driver code
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array");
int size = sc.nextInt();
int[] arr = new int[size];
System.out.println("Enter the elements of the array");
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}
System.out.println("Array before we Replace every element with the least greater element on its right is ");
ArrayList<int[]> temp = new ArrayList<int[]>();
for (int i = 0; i < size; i++) {
temp.add(new int[] { arr[i], i });
}
// we are sorting the temp according to the first of the pair i.e., value
Collections.sort(temp, (a, b) -> {
if (a[0] == b[0])
return a[1] - b[1];
return a[0] - b[0];
});
int[] arr2 = new int[size];
Arrays.fill(arr2, -1);
Stack<Integer> st = new Stack<Integer>();
for (int i = 0; i < size; i++) {
if (st.empty() || temp.get(i)[1] < st.peek())
st.push(temp.get(i)[1]);
// notice temp[i].second is the index
// Otherwise, if this index (i.e. temp[i].second) is bigger than the index placed at the top of the stack,
// we pop all the indexes saved at the top of the stack and make this index
// (i.e. temp[i].second) their next greater index.
else {
while (!st.empty() && temp.get(i)[1] > st.peek()) {
arr2[st.peek()] = temp.get(i)[1];
st.pop();
}
// push the current index to the stack
st.push(temp.get(i)[1]);
}
// we have initialize a result vector with all -1
int[] res = new int[size];
Arrays.fill(res, -1);
for (int k = 0; k < size; k++) {
// If there is no greater index after the index temp[i].second, the result is -1.
// otherwise, the result is the element of the array arr at index indexes[temp[i] .second]
if (arr2[temp.get(k)[1]] != -1)
res[temp.get(k)[1]] = arr[arr2[temp.get(k)[1]]];
}
}
int[] respond = arr2.clone();
System.out.println("Array after we Replace every element with the least greater element on its right is ");
for (int j = 0; j < respond.length; j++)
System.out.print(respond[j] + " ");
System.out.println();
}
}

Output

Complexity analysis

Time complexity

O(N), since we are using a loop to traverse the tree.

Space complexity

O(N), since we are using an array to take the data from the user for each node.

Optimized Approach

A different approach to the problem is to state our requirements and then think about them to develop a solution. If we go back through the array, we'll need a data structure(ds) to support:

ðŸ”ºInsert an element in sorted order into our data structure (so at any point in time the elements in our data structure are sorted).

ðŸ”ºdetermining the current element's upper bound (upper bound will give just a greater element from our data structure if present).

Algorithm

ðŸ”ºFirst of all, make a tree set data structure to perform the above-discussed approach as it provides a tree data structure for storage with the set interface.

ðŸ”ºTraversing the array in reverse order to add it to the treeset data structure.

ðŸ”ºNow we will use the following code to find if an upper bound(higher value) exists in the set then we will store it in the array at the same index.

ðŸ”ºIf there is no upper bound value then we will store -1 as indicated in the code.

Java Code

//java program to replace every element with the least greater element on its right
import java.util.*;
public class codingninjas2 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter the size of the array");
int size = sc.nextInt();
int[] arr = new int[size];
System.out.println("Enter the elements of the array");
for (int i = 0; i < size; i++) {
arr[i] = sc.nextInt();
}
System.out.println("Array before we Replace every element with the least greater element on its right is ");
for (int i : arr)
System.out.print(i + " ");
System.out.println();
TreeSet<Integer> s = new TreeSet<>();
for (int i = arr.length - 1; i >= 0; i--) {
s.add(arr[i]); // inserting the element into set
Integer it = s.higher(arr[i]); // finding out upper bound
if (it == null)
arr[i] = -1; // if upper_bound not exist then -1
else
arr[i] = it; // if upper_bound exists
}
System.out.println("Array after we Replace every element with the least greater element on its right is ");
for (int i : arr)
System.out.print(i + " ");
System.out.println();
}
}

Output

Complexity analysis

Time complexity

O(Nlog(N)), since we are inserting each element in our set and finding the upper bound for each element using a loop to replace every element with the least greater element on its right.

Space complexity

O(N), since we are using an array to take the data from the user for each node.

Frequently Asked Questions

What is the definition of a perfectly balanced tree?

If a tree is empty or the number of nodes in each subtree differs by no more than one, it is perfectly balanced. We know that searching the left or right subtree from any point will take the same amount of time in a perfectly balanced tree.

Is a complete binary tree a perfect binary tree?

All nodes in a full binary tree have either none or two children. All nodes up to level h could have two offspring in a complete binary tree of height h.

What is the height of a tree that is perfectly balanced?

One approach to achieve this is to ensure that our trees are evenly spaced in height. If the left subtree and right subtrees of any node are the same height, the tree is perfectly balanced. It is known that there are twice as many nodes at each level as there were at the preceding level, resulting in H = O(logN).

Conclusion

In this article, we have discussed the binary search tree data structure in brief, examples, approach, and how to replace every element with the least greater element on its right, time, and space complexity for the three approaches.