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 hl, int  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
Labels:

Comments

Post a Comment

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
1 comment
Read more

How to kill a process running on particular port in Linux

  If port 8080 needs to be kill use below single command: kill -9 $(lsof -t -i:8080) Note: remove -9 from the command, if you don't want to kill the process violently. To list any process listening to the port 8080: lsof -i:8080 Use any port number that you want to kill.
Post a Comment
Read more

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
1 comment
Read more