This post is completed by 2 users

  • 0
 Add to List
Medium

37. Get the Height of a Node in a Binary Tree

Objective: Given a binary tree, find the height of a given node in the tree.

Example:

Get The Height Of a Node

Approach - Recursion:

  1. Take a variable called height=0.
  2. Search for that given node in the tree using recursion.
  3. Each time you go left or right, increase the height by 1.
  4. Once you found the given node, return the height.
  5. If tree is over and the element is not found, return 0

 



public class Main {

    public static int getNodeHeight(Node root, Node x, int height){
        if(root==null) return 0;
        if(root==x) return height;

        //check if the node is present in the left sub tree
        int level = getNodeHeight(root.left,x,height+1);
        
        if(level!=0) return level;

        //check if the node is present in the right sub tree
        return getNodeHeight(root.right,x,height+1);
    }
    
    public static void main (String[] args) throws java.lang.Exception {
        Node root = new Node(5);
        root.left = new Node(10);
        root.right = new Node(15);
        root.left.left = new Node(20);
        Node x = new Node(25);
        root.left.right = x;
        root.left.right.left = new Node(35);
        System.out.println("Height of the Node " + x.data + " is : " +  getNodeHeight(root,x,1));
    }
}
class Node{
    int data;
    Node left;
    Node right;
    public Node(int data){
        this.data = data;
    }
}



class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def get_node_height(root, x, height):
    if not root:
        return 0
    if root == x:
        return height

    level = get_node_height(root.left, x, height + 1)

    if level != 0:
        return level

    return get_node_height(root.right, x, height + 1)

if __name__ == "__main__":
    root = Node(5)
    root.left = Node(10)
    root.right = Node(15)
    root.left.left = Node(20)
    x = Node(25)
    root.left.right = x
    root.left.right.left = Node(35)
    print("Height of the Node", x.data, "is :", get_node_height(root, x, 1))



package main

import "fmt"

type Node struct {
	data  int
	left  *Node
	right *Node
}

func getNodeHeight(root, x *Node, height int) int {
	if root == nil {
		return 0
	}
	if root == x {
		return height
	}

	level := getNodeHeight(root.left, x, height+1)

	if level != 0 {
		return level
	}

	return getNodeHeight(root.right, x, height+1)
}

func main() {
	root := &Node{data: 5}
	root.left = &Node{data: 10}
	root.right = &Node{data: 15}
	root.left.left = &Node{data: 20}
	x := &Node{data: 25}
	root.left.right = x
	root.left.right.left = &Node{data: 35}
	fmt.Println("Height of the Node", x.data, "is :", getNodeHeight(root, x, 1))
}

Output

Height of the Node 25 is : 3

Related Problems: