Question

JAVA (Tree height)

Define a new class named BSTWithHeight that extends BST with the following method:

/** Return the height of this binary tree */
public int height()

Class Name: Exercise25_01

Answer 1

public class BST {

   /* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;

public Node(int item) {
key = item;
left = right = null;
}
}

// Root of BST
Node root;

// Constructor
BST() {
root = null;
}

// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {

/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}

/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);

/* return the (unchanged) node pointer */
return root;
}

// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}

// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}

}

public class BSTwithHEight extends BST {

   static int height(Node node)
{
if (node == null)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = height(node.left);
int rDepth = height(node.right);

/* use the larger one */
if (lDepth > rDepth)
return (lDepth + 1);
else
return (rDepth + 1);
}
}
  
   public static void main(String[] args) {
       BSTwithHEight tree = new BSTwithHEight();
       tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
  
System.out.println("height is : "+height(tree.root));
  

   }

}