## Binary Tree sorting in java

Category : Data-structures-algorithms | Sub Category : Sorting Algorithms | By Runner Dev Last updated: 2020-10-31 19:11:42 Viewed : 197

Binary Tree sorting

A binary tree is a data structure in which an element has two successors(children). The left child is usually smaller than the parent, and the right child is usually bigger.

Worst complexity: n*log(n) (balanced)

Average complexity: n*log(n)

Best complexity: n*log(n)

Space complexity: n

Input:

51, 31, 71, 15, 7, 63, 23, 36, 89, 23, 32 Here , 51 root node

Step 1:    31 < 51 (less than the current node move to the left)

Step 2:    71 >51  (greater than the current node move to the right)

Step 3:   15 <51 and 15<31  (less than the current node move to the left to the left)

Step 4:    7 < 51 and 7<31 and 7<15 (less than the current node move to the left to the left to the left)

Step 5:    63>51 and 63<51 (less than the current node move to the right to the left)

Step 6:   23<51 and 23 < 31  and 15> 23 (less than the current node move to the left to the left to the right)

..vice versa elements will be added into the Binary tree

TreeSort.java

` package runnerdev; `

import java.util.Arrays;

public class TreeSort {

/** A node class representing each node in the binary search tree. */

static class Node {

int value;

Node left;

Node right;

public Node(int value) {

this.value = value;

left = null;

right = null;

}

}

Node node;

TreeSort() {

node = null;

}

/* insert a new key in Binary Sort Tree */

Node insert(Node node, int value) {

if (node == null) {

node = new Node(value);

return node;

}

/** If new node’s value is less than the current node move to the left. **/

if (value < node.value)

node.left = insert(node.left, value);

/** If new node’s value is greater than the current node move to the right. **/

else if (value > node.value)

node.right = insert(node.right, value);

return node;

}

// For traversing in order

public void inOrderAsc(Node node) {

if (node != null) {

inOrderAsc(node.left);

System.out.print(node.value + " ");

inOrderAsc(node.right);

}

}

public void inOrderDesc(Node node) {

if (node != null) {

inOrderDesc(node.right);

System.out.print(node.value + " ");

inOrderDesc(node.left);

}

}

/** Insert Array **/

void treeInsert(int array[]) {

for (int number : array) {

node = insert(node, number);

}

}

/** Binary tree create **/

public static TreeSort create() {

TreeSort tree = new TreeSort();

Node node = new Node(51);

tree.node = node;

tree.node.left = new Node(31);

tree.node.left.left = new Node(15);

tree.node.left.left.left = new Node(7);

tree.node.left.right = new Node(36);

tree.node.left.right.left = new Node(32);

tree.node.right = new Node(71);

tree.node.right.left = new Node(63);

return tree;

}

/**

* traverse the binary tree on InOrder traversal algorithm

*/

public void inOrder() {

inOrderAsc(node);

}

public static void main(String[] args) {

/** create Binary Tree **/

TreeSort treeSort = TreeSort.create();

// traversing binary tree using recursion

System.out.println("printing nodes of binary tree in Ascending order :");

treeSort.inOrder();

TreeSort tree = new TreeSort();

int array[] = {51, 31, 71, 15, 7, 63, 23, 36, 89, 23, 32 };

System.out.println(" Original array: " + Arrays.toString(array));

tree.treeInsert(array);

System.out.println("Ascending Order : ");

tree.inOrderAsc(tree.node);

System.out.println(" Descending Order : ");

tree.inOrderDesc(tree.node);

}

}

OutPut:

printing nodes of binary tree in Ascending order : 7 15 31 32 36 51 63 71

Original array: [51, 31, 71, 15, 7, 63, 23, 36, 89, 23, 32]

Ascending Order : 7 15 23 31 32 36 51 63 71 89

Descending Order : 89 71 63 51 36 32 31 23 15 7