Skip to main content

Find The Height of Binary Tree - Java Program

 Important points:
  • Height of tree = Number of edges in longest path from root to leaf
  • Height of a node = Number of edges in longest path from the node to a leaf node
  • Depth of a node = Number of edges in path from root to that node
  • Height of above tree is 3. Longest path is F -> B -> D -> E
  • Height of Node E is 0 and depth is 3. 
  • Depth of node B is 1 and height is 2. 

Pseudo Code:
FindHeight(root) {
if(root is NULL)
return -1; // return 0 if you want to count the node in the path
leftHeight <- FindHeight(root -> left)
rightHeight <- FindHeight(root -> right)
return max(lefHeight, rightHeight) + 1
}

JAVA PROGRAM:

public class BinTreeHeight {
static int max(int hlint  hr) {
if(hl > hr) {
return hl;
}
return hr;
}
static int treeHeight(Node n) {
int hl = 0;
int hr = 0;
if(n == null) {
return -1;
}
hl =  treeHeight(n.left);
hr =  treeHeight(n.right);
return max(hl, hr) + 1;
}
    
    public static void main(String a[]) {
    Node binTree = new Node(
    new Node(null, null, 5),
    new Node(
    new Node(null, null, 6),
    new Node(null, null, 9),
    8
),
    2
);
    
    System.out.println(treeHeight(binTree));
    }
}

//OUTPUT: 3

Comments

Popular posts from this blog

LinkList implementation with Insert, InsertAt, Delete Methods in Java

Linklist Representation  Node.java   public class Node { int data ; Node next ; Node( int data , Node next ){ this . data = data ; this . next = next ; } } LinkList.java public class LinkList { Node head ; public void insert( int data ) { Node node = new Node( data , null ); if ( head == null ) { head = node ; } else { Node currentNode = head ; while ( currentNode . next != null ) { currentNode = currentNode . next ; } currentNode . next = node ; } } public void inserAtStart( int data ) { Node node = new Node( data , null ); node . next = head ; head = node ; } public void insertAt( int index , int data ) { Node node = new Node( data , null ); // if index is 0 or head is null then insert at start if ( index == 0 || head == null ) { inserAtStart( data ); } els

Basics of Java Programming - Part 1

Datatypes in Java int 4 bytes short int 2 bytes long int 8 bytes byte 1 byte float  4 bytes double 8 bytes char 2 bytes Character to ASCII conversion in JAVA          class CharToASCII { public static void main(String a []) { char c1 = 'A' ; char c2 = 'a' ; System. out .print(( int ) c1 ); // OUTPUT: 65 System. out .print(( int ) c2 ); // OUTPUT: 97 System. out .print(( char )66); // OUTPUT: B  --> ASCII to i nt conversion           }        } "printf" is also available in JAVA            class  PrintfInJava {              public   static   void  main(String  a []) { int   i  =  4 ; int   j  =  7 ;                   int   k  =  i+j ; System. out .printf("Addition of %d and %d is %d", i, j, k);  // OUTPUT: 65            }        } Binary  Literals

"NodeJS Basics" Theory That You Should Know

To know better about NodeJS, you should know Javascript. So I start with Javascript Javascript is in top 3 language. JavaScript is developed on December 4, 1995. It was a client-side scripting language. So it was used only in browsers. Javascript uses  Javascript engine that is used by browsers to convert code into machine code. We have multiple JavaScript engines just like we have different browsers like Firefox, Chrome, internet explorer, edge etc. First JavaScript engine was SpiderMonkey developed by Netscape Communication by the creator of JavaScript Brendan Eich and it was developed in 10 days. Different browsers are using a different type of Javascript Engine:- Internet Explorer is using Chakra Firefox is using Spidermonkey Chrome is using V8 Microsoft Edge is rebuild using a chromium-based browser and now it is using V8 engine. Most Famous engine is now V8 Javascript engine because it is faster and can be used for mobile development, de