Skip to content

Instantly share code, notes, and snippets.

@wjx wjx/BBST.java
Last active Jan 16, 2017

Embed
What would you like to do?
Array to BST
//http://www.geeksforgeeks.org/sorted-array-to-balanced-bst/
//is the better solution(return created node, instead of a separated
//insert operation).
//Note here int mid = (int)Math.floor(n / 2); is used to get the middle
//node instead of int mid = (start + end) / 2;, resulting right middle
//node is selected when there is even number of nodes in the array.
import java.util.*;
import java.lang.*;
import java.io.*;
class BBST {
Node root;
class Node {
Node left;
Node right;
int key;
public Node(int v) {
key = v;
}
public Node getLeft() {
return left;
}
public void setLeft(Node node) {
left = node;
}
public Node getRight() {
return right;
}
public void setRight(Node node) {
right = node;
}
public int getKey() {
return key;
}
}
public BBST(int[] array) {
buildBST(array);
}
private void buildBST(int[] array) {
int n = array.length;
if (n == 0)
return;
int mid = (int)Math.floor(n / 2);
Node node = new Node(array[mid]);
insert(node, root);
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid + 1, n);
buildBST(left);
buildBST(right);
}
private void insert(Node newNode, Node parentNode) {
//for root
if (root == null) {
root = newNode;
return;
}
if (newNode.getKey() < parentNode.getKey()) {
if (parentNode.getLeft() == null)
parentNode.setLeft(newNode);
else
insert(newNode, parentNode.getLeft());
} else {
if (parentNode.getRight() == null)
parentNode.setRight(newNode);
else
insert(newNode, parentNode.getRight());
}
}
public void dump() {
preorderWalk(root);
}
private void preorderWalk(Node node) {
if (node == null)
return;
//root
System.out.print(node.getKey() + " ");
//left
preorderWalk(node.getLeft());
//right
preorderWalk(node.getRight());
}
}
class GFG {
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t > 0) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = sc.nextInt();
BBST bbst = new BBST(arr);
bbst.dump();
System.out.println();
t--;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.