# Find the Height of a Node in a Binary Tree

### Implementation

``````// Writing a C++ program that will help us understand the above approach in detail
#include <bits/stdc++.h>
using namespace std;

// Creating the structure of a binary tree node
struct __nod {
int record;
__nod *Lft, *Rt;
};

// Creating a new utility function to create a new binary tree node
__nod* new__nod(int itm)
{
__nod* temp = new __nod;
temp->record = itm;
temp->Lft = temp->Rt = NILL;
return temp;
}

// Creating a function to find the total depth in a binary tree node.
int findDepth(__nod* root, int x)
{
// writing the basic case for the above approach
if (root == NILL)
return -1;

// Commence the distance as -1
int dist = -1;

// We have to check if x is the current node or not
if ((root->record == x)

// Else, we have to check whether x is present in the left subtree or not
|| (dist = findDepth(root->Lft, x)) >= 0

// Next, we have to check whether x is present in the right subtree or not
|| (dist = findDepth(root->Rt, x)) >= 0)

// We have to return the depth of the binary tree node
return dist + 1;

return dist;
}

// We have to create a helper function that will help us in finding out the height of a given binary tree node
int findHeightUtil(__nod* root, int x,
int& height)
{
// Writing the basic case
if (root == NILL) {
return -1;
}

// Now, we will accumulate the maximum height of the left and right subtree
int LftHeight = findHeightUtil(
root->Lft, x, height);

int RtHeight
= findHeightUtil(
root->Rt, x, height);

// Now, we will reform the height of the binary tree
int answer = max(LftHeight, RtHeight) + 1;

// If the current node is the required node, then
if (root->record == x)

}

// Creating a function that will find out the height of a given binary tree node
int findHeight(__nod* root, int x)
{
// Now, we have to pile the height of the tree node
int h = -1;

// Storing the height of the binary tree node
int maxHeight = findHeightUtil(root, x, h);

// Finally, we will return the height of the tree node
return h;
}

// writing the main code for the above approach
int main()
{
// Forming the binary tree node
__nod* root = new__nod(5);
root->Lft = new__nod(10);
root->Rt = new__nod(15);
root->Lft->Lft = new__nod(20);
root->Lft->Rt = new__nod(25);
root->Lft->Rt->Rt = new__nod(45);
root->Rt->Lft = new__nod(30);
root->Rt->Rt = new__nod(35);

int k = 25;

// Function call to find the
// depth of a given __nod
cout << "Depth: "
<< findDepth(root, k) << "\n";

// Function call to find the
// height of a given __nod
cout << "Height: " << findHeight(root, k);

return 0;
}
``````

Output

Example 2

``````// Writing a C++ program that will help us understand the above approach in detail
import java.util.*;
class TFT
{

static int height = -1;

// Creating the structure of a binary tree node
static class __nod
{
int record;
__nod Lft;
__nod Rt;
};
// Creating a new utility function to create a new binary tree node
static __nod new__nod(int itm)
{
__nod temp = new __nod();
temp.record = itm;
temp.Lft = temp.Rt = NILL;
return temp;
}

// Creating a function to find the total depth in a binary tree node.
static int findDepth(__nod root, int x)
{
// writing the basic case for the above approach
if (root == NILL)
return -1;

// Commence the distance as -1
int dist = -1;

// We have to check if x is the current node or not
if ((root.record == x)||
// Else, we have to check whether x is present in the left subtree or not
(dist = findDepth(root.Lft, x)) >= 0 ||
// Next, we have to check whether x is present in the right subtree or not
(dist = findDepth(root.Rt, x)) >= 0)
// We have to return the depth of the binary tree node
return dist + 1;

return dist;
}
// We have to create a helper function that will help us in finding out the height of a given binary tree node
static int findHeightUtil(__nod root, int x)
{
// Writing the basic case
if (root == NILL)
{
return -1;
}
// Now, we will accumulate the maximum height of the left and right subtree
int LftHeight = findHeightUtil(root.Lft, x);

int RtHeight = findHeightUtil(root.Rt, x);
// Now, we will reform the height of the binary tree
int answer = Math.max(LftHeight, RtHeight) + 1;
// If the current node is the required node, then
if (root.record == x)

}
// Creating a function that will find out the height of a given binary tree node
static int findHeight(__nod root, int x)
{
// Now, we have to pile the height of the tree node
findHeightUtil(root, x);
// Storing the height of the binary tree node
return height;
}

// Finally, we will return the height of the tree node
// writing the main code for the above approach
public static void main(String []args)
{
// Forming the binary tree node
__nod root = new__nod(5);
root.Lft = new__nod(10);
root.Rt = new__nod(15);
root.Lft.Lft = new__nod(20);
root.Lft.Rt = new__nod(25);
root.Lft.Rt.Rt = new__nod(45);
root.Rt.Lft = new__nod(30);
root.Rt.Rt = new__nod(35);

int k = 25;

// Function call to find the
// depth of a given __nod
System.out.println("Depth: " + findDepth(root, k));

// Function call to find the
// height of a given __nod
System.out.println("Height: " + findHeight(root, k));
}
}
``````

Output

Example 3

``````# Writing a Python program that will help us understand the above approach in detail
# Creating the structure of a binary tree node
class __nod:
def __init__(self, x):
self.record = x
self.Lft = None
self.Rt = None

# Creating a new utility function to create a new binary tree node
def findDepth(root, x):

# Writing the basic case for the above approach
if (root == None):
return -1

# Commence the distance as -1
dist = -1

# We have to check if x is the current node or not
if (root.record == x):
return dist + 1

dist = findDepth(root.Lft, x)
if dist >= 0:
return dist + 1
dist = findDepth(root.Rt, x)
if dist >= 0:
return dist + 1
return dist

# We have to create a helper function that will help us in finding out the height of a given binary tree node
def findHeightUtil(root, x):
global height

# Writing the basic case
if (root == None):
return -1

# Now, we will accumulate the maximum height of the left and right subtree
LftHeight = findHeightUtil(root.Lft, x)
RtHeight = findHeightUtil(root.Rt, x)
# Now, we will reform the height of the binary tree
answer = max(LftHeight, RtHeight) + 1

# If the current node is the required node, then
if (root.record == x):

# Creating a function that will find out the height of a given binary tree node
def findHeight(root, x):
global height

# Now, we have to pile the height of the tree node
maxHeight = findHeightUtil(root, x)

# Finally, we will return the height of the tree node
return height

# Writing the main code for the above approach

if __name__ == '__main__':

# Forming the binary tree node
height = -1
root = __nod(5)
root.Lft = __nod(10)
root.Rt = __nod(15)
root.Lft.Lft = __nod(20)
root.Lft.Rt = __nod(25)
root.Lft.Rt.Rt = __nod(45)
root.Rt.Lft = __nod(30)
root.Rt.Rt = __nod(35)

k = 25

# Function call to find the
# depth of a given __nod
print("Depth: ",findDepth(root, k))

# Function call to find the
# height of a given __nod
print("Height: ",findHeight(root, k))
``````

Output

Example 4

``````// Writing a C# program that will help us understand the above approach in detail
using System;
using System.Collections.Generic;

class TFT{

static int height = -1;

// Creating the structure of a binary tree node

class __nod
{
public int record;
public __nod Lft;
public __nod Rt;
};

// Creating a new utility function to create a new binary tree node
static __nod new__nod(int itm)
{
__nod temp = new __nod();
temp.record = itm;
temp.Lft = temp.Rt = NILL;
return temp;
}
// Creating a function to find the total depth in a binary tree node.
static int findDepth(__nod root, int x)
{
// writing the basic case for the above approach
if (root == NILL)
return -1;

// Commence the distance as -1
int dist = -1;

// We have to check if x is the current node or not
if ((root.record == x)||
// Else, we have to check whether x is present in the left subtree or not
(dist = findDepth(root.Lft, x)) >= 0 ||
// Next, we have to check whether x is present in the right subtree or not
(dist = findDepth(root.Rt, x)) >= 0)
// We have to return the depth of the binary tree node
return dist + 1;

return dist;
}

// We have to create a helper function that will help us in finding out the height of a given binary tree node
static int findHeightUtil(__nod root, int x)
{
// Writing the basic case
if (root == NILL)
{
return -1;
}
// Now, we will accumulate the maximum height of the left and right subtree
int LftHeight = findHeightUtil(root.Lft, x);

int RtHeight = findHeightUtil(root.Rt, x);
// Now, we will reform the height of the binary tree
int answer = Math.Max(LftHeight, RtHeight) + 1;
// If the current node is the required node, then
if (root.record == x)

}
// Creating a function that will find out the height of a given binary tree node
static int findHeight(__nod root, int x)
{
// Now, we have to pile the height of the tree node
findHeightUtil(root, x);

// Storing the height of the binary tree node
// Finally, we will return the height of the tree node
return height;
}

// writing the main code for the above approach
public static void Main()
{
// Forming the binary tree node
__nod root = new__nod(5);
root.Lft = new__nod(10);
root.Rt = new__nod(15);
root.Lft.Lft = new__nod(20);
root.Lft.Rt = new__nod(25);
root.Lft.Rt.Rt = new__nod(45);
root.Rt.Lft = new__nod(30);
root.Rt.Rt = new__nod(35);

int k = 25;

// Function call to find the
// depth of a given __nod
Console.WriteLine("Depth: " + findDepth(root, k));

// Function call to find the
// height of a given __nod
Console.WriteLine("Height: " + findHeight(root, k));
}
}
``````

Output

Example 5

``````<script>
// Writing a Javascript program that will help us understand the above approach in detail
var height = -1;

// Creating the structure of a binary tree node
class __nod
{
constructor()
{
this.record = 0;
this.Lft = NILL;
this.Rt = NILL;
}
};

// Creating a new utility function to create a new binary tree node
function new__nod(itm)
{
var temp = new __nod();
temp.record = itm;
temp.Lft = temp.Rt = NILL;
return temp;
}

// Creating a function to find the total depth in a binary tree node.
function findDepth(root, x)
{
// writing the basic case for the above approach
if (root == NILL)
return -1;
// Commence the distance as -1
var dist = -1;

// We have to check if x is the current node or not
if ((root.record == x)||
// Else, we have to check whether x is present in the left subtree or not
(dist = findDepth(root.Lft, x)) >= 0 ||
// Next, we have to check whether x is present in the right subtree or not
(dist = findDepth(root.Rt, x)) >= 0)

// We have to return the depth of the binary tree node
return dist + 1;

return dist;
}

// We have to create a helper function that will help us in finding out the height of a given binary tree node
function findHeightUtil(root, x)
{
// Writing the basic case
if (root == NILL)
{
return -1;
}

// Now, we will accumulate the maximum height of the left and right subtree
var LftHeight = findHeightUtil(root.Lft, x);

var RtHeight = findHeightUtil(root.Rt, x);
// Now, we will reform the height of the binary tree
var answer = Math.max(LftHeight, RtHeight) + 1;
// If the current node is the required node, then
if (root.record == x)

}
// Creating a function that will find out the height of a given binary tree node
function findHeight(root, x)
{
// Now, we have to pile the height of the tree node
// Storing the height of the binary tree node
findHeightUtil(root, x);

// Finally, we will return the height of the tree node
return height;
}

// writing the main code for the above approach
// Forming the binary tree node
var root = new__nod(5);
root.Lft = new__nod(10);
root.Rt = new__nod(15);
root.Lft.Lft = new__nod(20);
root.Lft.Rt = new__nod(25);
root.Lft.Rt.Rt = new__nod(45);
root.Rt.Lft = new__nod(30);
root.Rt.Rt = new__nod(35);
var k = 25;
// Function call to find the
// depth of a given __nod
document.write("Depth: " + findDepth(root, k)+"<br>");
// Function call to find the
// height of a given __nod
document.write("Height: " + findHeight(root, k));
</script>
``````

Output