JAVA: The Height of a Binary Tree To start, a node in a binary tree looks like t

Question

JAVA: The Height of a Binary Tree

To start, a node in a binary tree looks like the following, in terms of Java:

public class BinaryTreeNode {

int key;

BinaryTreeNode left, right, parent;

public BinaryTreeNode(int key){

this.key=key;

left=right=parent=null; }

}

And a binary tree looks like the following:

public class BinaryTree {

BinaryTreeNode root;

public BinaryTree(){

root=null; }

}

Okay so WHAT TO DO:

implement at least the Insertion operation, either non-recursively or recursively.

MAIN PART: You need a method, with its signature being int treeHeight(BinaryTreeNode root), that gives the height of any tree with its top node referred by the root parameter.

Here is the recursive opertion:

Explanation / Answer

Implemented the given algorithm and also the logic to compute the height of tree.

JAVA CODE

public class BinaryTree {

   BinaryTreeNode root;

   //Constructor to initialize root to null.
   public BinaryTree(){
       root=null;
   }

   // Function to insert into binary tree.
   // According to given algorithm here y is parent, x is the current node and
   // z is the new node to be inserted
   public void BinaryTreeInsert(BinaryTreeNode parent, BinaryTreeNode currNode,
           BinaryTreeNode newNode) {
       // check if we have reach the end of tree.
       if(currNode != null) {
           // we need to traverse the tree till we reach leaf.
           // check if we should go left or right depending on values.
           if(newNode.key < currNode.key)
               BinaryTreeInsert(currNode, currNode.left, newNode);
           else
               BinaryTreeInsert(currNode, currNode.right, newNode);
           return;
       }

       newNode.parent = parent;
       // root node parent is null.
       if(parent == null) {
           root = newNode;
       }
       // if key is smaller than parent's key insert into left
       else if(newNode.key < parent.key){
           parent.left = newNode;
       }
//       if key is greater than parent's key insert into right
       else {
           parent.right = newNode;
       }
   }

   // Inorder traversal of tree. should result into sorted order of binary tree.
   private void inOrderUtility(BinaryTreeNode node) {
       if(node != null) {
           inOrderUtility(node.left);
           System.out.println(node.key + " ");
           inOrderUtility(node.right);
       }
   }
   // function to print inoder traversal.
   public void printInOrder() {
       inOrderUtility(root);
   }
   public static void main(String[] args) {

       // Inserting nodes in BST.
       BinaryTree bst = new BinaryTree();
       BinaryTreeNode newNode = new BinaryTreeNode(50);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       newNode = new BinaryTreeNode(30);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       newNode = new BinaryTreeNode(20);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       newNode = new BinaryTreeNode(40);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       newNode = new BinaryTreeNode(70);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       newNode = new BinaryTreeNode(60);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       newNode = new BinaryTreeNode(80);
       bst.BinaryTreeInsert(null, bst.root, newNode);

       bst.printInOrder();
      
       // Computing the height of tree.
       int ht = treeHeight(bst.root);
       System.out.println("Height of tree : "+ht);

   }

   private static int treeHeight(BinaryTreeNode root) {
       // if the node is null return 0;
       if(root == null) {
           return 0;
       }
       // if it is leaf node then height is zero.
       if(root.left == null && root.right == null) {
           return 0;
       }
      
       // return the maximum of height of left subtree and right subtree.
       return Math.max(treeHeight(root.left), treeHeight(root.right)) + 1;
      
   }

}

Sample output

20
30
40
50
60
70
80
Height of tree : 2

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.