Showing posts with label Binary Search Tree Height. Show all posts
Showing posts with label Binary Search Tree Height. Show all posts ## How to get height of BST using recursive way

The height of a Binary Search Tree is the length of the longest downward path to a leaf from root node. This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has height −1.
In below example the height of the tree is 5, i.e., from root(10) which goes to 3 -> 5 -> 7 -> 8 -> 9. So maximum height of the tree is 5

Lets see simple Java code to get the height of a BST tree using recursion.

```class Node {
Node left, right;
int data;

public Node(int data) {
this.data = data;
}
}

public class TreeHeight {

public static void main(String[] args) {

int a[] = { 1, 2, 3, 4, -1, -2, -3, -4, -5 };
//int a[] = { 10,3,15,2,5,19,7,8,9,20,1 };

Node root = null;
TreeHeight tree = new TreeHeight();

for (int i = 0; i < a.length; i++) {
root = tree.insertNode(root, a[i]);
}

int height = tree.getBSTHeight(root);
System.out.println("Binary Tree maximum height : " + height);
}

public int getBSTHeight(Node node) {
if (node != null)
return Math.max(getBSTHeight(node.left), ```
```                                        getBSTHeight(node.right)) + 1;
else
return -1;
}

public Node insertNode(Node root, int data) {
Node currentNode = new Node(data);
if (root == null) {
root = currentNode;
} else {
insertData(currentNode, root);
}
return root;
}

public Node insertData(Node newNode, Node root) {

if (root.data < newNode.data) {
if (root.right == null) {
root.right = newNode;
} else {
return insertData(newNode, root.right);
}
} else if (root.data > newNode.data) {
if (root.left == null) {
root.left = newNode;
} else {
return insertData(newNode, root.left);
}
}
return root;
}
}
```

OUTPUT:

```Binary Tree maximum height : 5
```