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

Blockchain in Theory - Blockchain, Bitcoin, Mining

   Blockchain is the software protocol that tell the Internet how to transfer money and assets. Blockchain is the layer and Bitcoin is the application. Just one of many cryptocurrency kinds of applications. When one user send email to another then both users do not have to know about the underlaying process except email address. Similarly,  User don't need to know anything other than other user's wallet address to send some bitcoin or other cryptocurrencies.  Any file on Internet may have multiple copies but money is something that should not be copied multiple times. This has been a longstanding problem in computing networks namely the double spend problem. Satoshi Nakamoto introduced white paper for digital cash system in 2008 to resolve the double spending problem and fortified by a ledger which enforces the money is only spent once. It took 15 years alone for corporate email as the main application to be a standard thing in our lives. And similarly the money Internet block

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.

How to Setup Virtual Environment in Python with venv

A virtual environment is the most used tool by the developers to isolate the dependencies for different projects. Suppose you have two projects say porj1 and proj2 . proj1 needs the Django dependency with version 3.2 but your proj2 needs the Django dependency with version 2.2. In this situation you need a virtual environment to keep the both version on your system separately.  How to create virtual environment in python:  Decide a directory where you want to create the virtual environment. You can use your project directory or any other directory as per your wish.  Run the below command. Here` awesome_proj_env ` is the folder where virtual environment will be created. if the folder does not exists then it will be created automatically. python3 -m venv awesome_proj_env    Activate the virtual environment: On Linux/Mac OSX: source awesome_proj_env/bin/activate  On Windows: awesome_proj_env \Scripts\activate.bat Deactivate the virtual environment in Python: type " deactivate "