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)
		height = answer;


	return answer;
}


// 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)
		height = answer;


	return answer;
}
// 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):
		height = answer


	return answer


# 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)
		height = answer;


	return answer;
}
// 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)
		height = answer;


	return answer;
}
// 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