Find the Maximum Depth or Height of given Binary Tree

Last Updated : 03 Oct, 2023

Given a binary tree, the task is to find the height of the tree. The height of the tree is the number of vertices in the tree from the root to the deepest node.

Note: The height of an empty tree is 0 and the height of a tree with single node is 1.

Example of Binary Tree

Example of Binary Tree

Recursively calculate the height of the left and the right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below the pseudo code and program for details.

Illustration:

Consider the following tree:

Example of Tree
maxDepth(‘1’) = max(maxDepth(‘2’), maxDepth(‘3’)) + 1 = 2 + 1

because recursively
maxDepth(‘2’) = max (maxDepth(‘4’), maxDepth(‘5’)) + 1 = 1 + 1 and (as height of both ‘4’ and ‘5’ are 1)
maxDepth(‘3’) = 1

Follow the below steps to Implement the idea:

Recursively do a Depth-first search.
If the tree is empty then return 0
Otherwise, do the following
- Get the max depth of the left subtree recursively i.e. call maxDepth( tree->left-subtree)
- Get the max depth of the right subtree recursively i.e. call maxDepth( tree->right-subtree)
- Get the max of max depths of left and right subtrees and add 1 to it for the current node.
  - $max_depth = max(max dept of left subtree, max depth of right subtree) + 1$
Return max_depth.

Below is the Implementation of the above approach:

C++

// C++ program to find height of tree
#include <bits/stdc++.h>
using namespace std;
 
/* A binary tree node has data, pointer to left child
and a pointer to right child */
class node {
public:
    int data;
    node* left;
    node* right;
};
 
/* Compute the "maxDepth" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int maxDepth(node* node)
{
    if (node == NULL)
        return 0;
    else {
        /* compute the depth of each subtree */
        int lDepth = maxDepth(node->left);
        int rDepth = maxDepth(node->right);
 
        /* use the larger one */
        if (lDepth > rDepth)
            return (lDepth + 1);
        else
            return (rDepth + 1);
    }
}
 
/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
node* newNode(int data)
{
    node* Node = new node();
    Node->data = data;
    Node->left = NULL;
    Node->right = NULL;
 
    return (Node);
}
 
// Driver code
int main()
{
    node* root = newNode(1);
 
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    cout << "Height of tree is " << maxDepth(root);
    return 0;
}
 
// This code is contributed by Amit Srivastav

C

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node {
    int data;
    struct node* left;
    struct node* right;
};
 
/* Compute the "maxDepth" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
int maxDepth(struct node* node)
{
    if (node == NULL)
        return 0;
    else {
        /* compute the depth of each subtree */
        int lDepth = maxDepth(node->left);
        int rDepth = maxDepth(node->right);
 
        /* use the larger one */
        if (lDepth > rDepth)
            return (lDepth + 1);
        else
            return (rDepth + 1);
    }
}
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node
        = (struct node*)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
 
    return (node);
}
 
int main()
{
    struct node* root = newNode(1);
 
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    printf("Height of tree is %d", maxDepth(root));
 
    getchar();
    return 0;
}

Java

// Java program to find height of tree
 
// A binary tree node
class Node {
    int data;
    Node left, right;
 
    Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
class BinaryTree {
    Node root;
 
    /* Compute the "maxDepth" of a tree -- the number of
       nodes along the longest path from the root node
       down to the farthest leaf node.*/
    int maxDepth(Node node)
    {
        if (node == null)
            return 0;
        else {
            /* compute the depth of each subtree */
            int lDepth = maxDepth(node.left);
            int rDepth = maxDepth(node.right);
 
            /* use the larger one */
            if (lDepth > rDepth)
                return (lDepth + 1);
            else
                return (rDepth + 1);
        }
    }
 
    /* Driver program to test above functions */
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        System.out.println("Height of tree is "
                           + tree.maxDepth(tree.root));
    }
}
 
// This code has been contributed by Amit Srivastav

Python3

# Python3 program to find the maximum depth of tree
 
# A binary tree node
 
 
class Node:
 
    # Constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
 
# Compute the "maxDepth" of a tree -- the number of nodes
# along the longest path from the root node down to the
# farthest leaf node
 
 
def maxDepth(node):
    if node is None:
        return 0
 
    else:
 
        # Compute the depth of each subtree
        lDepth = maxDepth(node.left)
        rDepth = maxDepth(node.right)
 
        # Use the larger one
        if (lDepth > rDepth):
            return lDepth+1
        else:
            return rDepth+1
 
 
# Driver program to test above function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
 
 
print("Height of tree is %d" % (maxDepth(root)))
 
# This code is contributed by Amit Srivastav

C#

// C# program to find height of tree
using System;
 
// A binary tree node
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
 
public class BinaryTree {
    Node root;
 
    /* Compute the "maxDepth" of a tree -- the number of
    nodes along the longest path from the root node
    down to the farthest leaf node.*/
    int maxDepth(Node node)
    {
        if (node == null)
            return 0;
        else {
            /* compute the depth of each subtree */
            int lDepth = maxDepth(node.left);
            int rDepth = maxDepth(node.right);
 
            /* use the larger one */
            if (lDepth > rDepth)
                return (lDepth + 1);
            else
                return (rDepth + 1);
        }
    }
 
    /* Driver code */
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
 
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        Console.WriteLine("Height of tree is "
                          + tree.maxDepth(tree.root));
    }
}
 
// This code has been contributed by
// Correction done by Amit Srivastav

Javascript

<script>
 
// JavaScript program to find height of tree
 
// A binary tree node
class Node
{
    constructor(item)
    {
        this.data=item;
        this.left=this.right=null;
    }
}
 
    let root;
     
     /* Compute the "maxDepth" of a tree -- the number of
       nodes along the longest path from the root node
       down to the farthest leaf node.*/
    function maxDepth(node)
    {
        if (node == null)
            return 0;
        else
        {
            /* compute the depth of each subtree */
            let lDepth = maxDepth(node.left);
            let rDepth = maxDepth(node.right);
   
            /* use the larger one */
            if (lDepth > rDepth)
                return (lDepth + 1);
             else
                return (rDepth + 1);
        }
    }
     
    /* Driver program to test above functions */
     
        root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
   
        document.write("Height of tree is : " +
                                      maxDepth(root));
 
 
 
 
// This code is contributed by rag2127
//Correction done by Amit Srivastav
 
</script>

Output

Height of tree is 3

Time Complexity: O(N) (Please see the post on Tree Traversal for details)
Auxiliary Space: O(N) due to recursive stack.

Find the Maximum Depth or Height of a Tree using Level Order Traversal:

Do Level Order Traversal, while adding Nodes at each level to Queue, we have to add NULL Node so that whenever it is encountered, we can increment the value of variable and that level get counted.

Follow the below steps to Implement the idea:

Traverse the tree in level order traversal starting from root.
- Initialize an empty queue Q, a variable depth and push root, then push null into the Q.
- Run a while loop till Q is not empty.
  - Store the front element of Q and Pop out the front element.
  - If the front of Q is NULL then increment depth by one and if queue is not empty then push NULL into the Q.
  - Else if the element is not NULL then check for its left and right children and if they are not NULL push them into Q.
Return depth.

Below is the Implementation of the above approach:

C++

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// A Tree node
struct Node {
    int key;
    struct Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
 
/*Function to find the height(depth) of the tree*/
int height(struct Node* root)
{
 
    // Initialising a variable to count the
    // height of tree
    int depth = 0;
 
    queue<Node*> q;
 
    // Pushing first level element along with NULL
    q.push(root);
    q.push(NULL);
    while (!q.empty()) {
        Node* temp = q.front();
        q.pop();
 
        // When NULL encountered, increment the value
        if (temp == NULL) {
            depth++;
        }
 
        // If NULL not encountered, keep moving
        if (temp != NULL) {
            if (temp->left) {
                q.push(temp->left);
            }
            if (temp->right) {
                q.push(temp->right);
            }
        }
 
        // If queue still have elements left,
        // push NULL again to the queue.
        else if (!q.empty()) {
            q.push(NULL);
        }
    }
    return depth;
}
 
// Driver program
int main()
{
    // Let us create Binary Tree shown in above example
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
 
    root->left->left = newNode(4);
    root->left->right = newNode(5);
 
    cout << "Height(Depth) of tree is: " << height(root);
}

Java

// Java program for above approach
import java.util.LinkedList;
import java.util.Queue;
 
class GFG {
 
    // A tree node structure
    static class Node {
        int key;
        Node left;
        Node right;
    }
 
    // Utility function to create
    // a new node
    static Node newNode(int key)
    {
        Node temp = new Node();
        temp.key = key;
        temp.left = temp.right = null;
        return temp;
    }
 
    /*Function to find the height(depth) of the tree*/
    public static int height(Node root)
    {
 
        // Initialising a variable to count the
        // height of tree
        int depth = 0;
 
        Queue<Node> q = new LinkedList<>();
 
        // Pushing first level element along with null
        q.add(root);
        q.add(null);
        while (!q.isEmpty()) {
            Node temp = q.peek();
            q.remove();
 
            // When null encountered, increment the value
            if (temp == null) {
                depth++;
            }
 
            // If null not encountered, keep moving
            if (temp != null) {
                if (temp.left != null) {
                    q.add(temp.left);
                }
                if (temp.right != null) {
                    q.add(temp.right);
                }
            }
 
            // If queue still have elements left,
            // push null again to the queue.
            else if (!q.isEmpty()) {
                q.add(null);
            }
        }
        return depth;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        Node root = newNode(1);
        root.left = newNode(2);
        root.right = newNode(3);
 
        root.left.left = newNode(4);
        root.left.right = newNode(5);
 
        System.out.println("Height(Depth) of tree is: "
                           + height(root));
    }
}
 
// This code is contributed by jana_sayantan.

Python3

# Python code to implement the approach
 
# A Tree node
 
 
class Node:
 
    def __init__(self):
        self.key = 0
        self.left, self.right = None, None
 
# Utility function to create a new node
 
 
def newNode(key):
 
    temp = Node()
    temp.key = key
    temp.left, temp.right = None, None
    return temp
 
 
# Function to find the height(depth) of the tree
def height(root):
 
    # Initialising a variable to count the
    # height of tree
    depth = 0
 
    q = []
 
    # appending first level element along with None
    q.append(root)
    q.append(None)
    while(len(q) > 0):
        temp = q[0]
        q = q[1:]
 
        # When None encountered, increment the value
        if(temp == None):
            depth += 1
 
        # If None not encountered, keep moving
        if(temp != None):
            if(temp.left):
                q.append(temp.left)
 
            if(temp.right):
                q.append(temp.right)
 
        # If queue still have elements left,
        # append None again to the queue.
        elif(len(q) > 0):
            q.append(None)
    return depth
 
# Driver program
 
 
# Let us create Binary Tree shown in above example
root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
 
root.left.left = newNode(4)
root.left.right = newNode(5)
 
print(f"Height(Depth) of tree is: {height(root)}")
 
 
# This code is contributed by shinjanpatra

C#

// C# Program to find the Maximum Depth or Height of Binary Tree
using System;
using System.Collections.Generic;
 
// A Tree node
public class Node {
    public int data;
    public Node left, right;
 
    public Node(int item)
    {
        data = item;
        left = null;
        right = null;
    }
}
 
public class BinaryTree {
 
    Node root;
 
    // Function to find the height(depth) of the tree
    int height()
    {
        // Initialising a variable to count the
        // height of tree
        int depth = 0;
 
        Queue<Node> q = new Queue<Node>();
 
        // Pushing first level element along with NULL
        q.Enqueue(root);
        q.Enqueue(null);
        while (q.Count != 0) {
            Node temp = q.Dequeue();
 
            // When NULL encountered, increment the value
            if (temp == null)
                depth++;
 
            // If NULL  not encountered, keep moving
            if (temp != null) {
                if (temp.left != null) {
                    q.Enqueue(temp.left);
                }
                if (temp.right != null) {
                    q.Enqueue(temp.right);
                }
            }
 
            // If queue still have elements left,
            // push NULL again to the queue
            else if (q.Count != 0) {
                q.Enqueue(null);
            }
        }
        return depth;
    }
 
    // Driver program
    public static void Main()
    {
        // Let us create Binary Tree shown in above example
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
 
        Console.WriteLine("Height(Depth) of tree is: "
                          + tree.height());
    }
}
 
// This code is contributed by Yash Agarwal(yashagarwal2852002)

Javascript

<script>
 
// JavaScript code to implement the approach
 
// A Tree node
class Node{
 
    constructor(){
        this.key = 0
        this.left = null
        this.right = null
    }
 
}
 
// Utility function to create a new node
function newNode(key){
 
    let temp = new Node()
    temp.key = key
    temp.left = null
    temp.right = null
    return temp
 
}
 
// Function to find the height(depth) of the tree
function height(root){
 
    // Initialising a variable to count the
    // height of tree
    let depth = 0
 
    let q = []
     
    // pushing first level element along with null
    q.push(root)
    q.push(null)
    while(q.length>0){
        let temp = q.shift()
     
        // When null encountered, increment the value
        if(temp == null)
            depth += 1
         
        // If null not encountered, keep moving
        if(temp != null){
            if(temp.left)
                q.push(temp.left)
             
            if(temp.right)
                q.push(temp.right)
        }
             
        // If queue still have elements left,
        // push null again to the queue.
        else if(q.length>0)
            q.push(null)
    }
    return depth
 
}
 
// Driver program
 
// Let us create Binary Tree shown in above example
let root = newNode(1)
root.left = newNode(2)
root.right = newNode(3)
 
root.left.left = newNode(4)
root.left.right = newNode(5)
 
document.write(`Height(Depth) of tree is: ${height(root)}`,"</br>")
 
// This code is contributed by shinjanpatra
 
</script>

Output

Height(Depth) of tree is: 3

Time Complexity: O(N)
Auxiliary Space: O(N)

Another method to find height using Level Order Traversal:

This method also uses the concept of Level Order Traversal but we wont be adding null in the Queue. Simply increase the counter when the level increases and push the children of current node into the queue, then remove all the nodes from the queue of the current Level.

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// A Tree node
struct Node {
  int key;
  struct Node *left, *right;
};
 
// Utility function to create a new node
Node* newNode(int key)
{
  Node* temp = new Node;
  temp->key = key;
  temp->left = temp->right = NULL;
  return (temp);
}
 
/*Function to find the height(depth) of the tree*/
int height(Node* root)
{
 
  // Initialising a variable to count the
  // height of tree
  queue<Node*> q;
  q.push(root);
  int height = 0;
  while (!q.empty()) {
    int size = q.size();
    for (int i = 0; i < size; i++) {
      Node* temp = q.front();
      q.pop();
      if (temp->left != NULL) {
        q.push(temp->left);
      }
      if (temp->right != NULL) {
        q.push(temp->right);
      }
    }
    height++;
  }
  return height;
}
 
// Driver program
int main()
{
 
  // Let us create Binary Tree shown in above example
  Node* root = newNode(1);
  root->left = newNode(2);
  root->right = newNode(3);
 
  root->left->left = newNode(4);
  root->left->right = newNode(5);
 
  cout << "Height(Depth) of tree is: " << height(root);
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Java

// Java program for above approach
import java.util.LinkedList;
import java.util.Queue;
 
class GFG {
 
    // A tree node structure
    static class Node {
        int key;
        Node left;
        Node right;
    }
 
    // Utility function to create
    // a new node
    static Node newNode(int key)
    {
        Node temp = new Node();
        temp.key = key;
        temp.left = temp.right = null;
        return temp;
    }
 
    /*Function to find the height(depth) of the tree*/
    public static int height(Node root)
    {
 
        // Initialising a variable to count the
        // height of tree
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        int height = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                Node temp = q.poll();
                if (temp.left != null) {
                    q.add(temp.left);
                }
                if (temp.right != null) {
                    q.add(temp.right);
                }
            }
            height++;
        }
        return height;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        Node root = newNode(1);
        root.left = newNode(2);
        root.right = newNode(3);
 
        root.left.left = newNode(4);
        root.left.right = newNode(5);
 
        System.out.println("Height(Depth) of tree is: "
                           + height(root));
    }
}

Python3

# Python3 program to find the height of a tree 
   
# A binary tree node 
class Node: 
   
    # Constructor to create a new node 
    def __init__(self, data): 
        self.key = data 
        self.left = None
        self.right = None
   
# Function to find height of tree 
def height(root): 
    # Base Case 
    if root is None: 
        return 0
   
    # Create an empty queue for level order traversal 
    q = [] 
   
    # Enqueue Root and initialize height 
    q.append(root) 
    height = 0
   
    # Loop while queue is not empty 
    while q: 
   
        # nodeCount (queue size) indicates number of nodes 
        # at current level 
        nodeCount = len(q) 
   
        # Dequeue all nodes of current level and Enqueue all 
        # nodes of next level 
        while nodeCount > 0: 
            node = q.pop(0) 
            if node.left is not None: 
                q.append(node.left) 
            if node.right is not None: 
                q.append(node.right) 
            nodeCount -= 1
        height += 1
   
    return height 
   
# Driver Code 
root = Node(1) 
root.left = Node(2) 
root.right = Node(3) 
root.left.left = Node(4) 
root.left.right = Node(5) 
   
print("Height(Depth) of tree is", height(root))

C#

using System;
using System.Collections.Generic;
 
class GFG {
 
  // A Tree node
  class Node {
    public int key;
    public Node left, right;
 
    public Node(int key)
    {
      this.key=key;
      this.left=this.right=null;
    }
  }
 
  // Utility function to create a new node
  /*Node newNode(int key)
    {
      Node* temp = new Node;
      temp.key = key;
      temp.left = temp.right = NULL;
      return (temp);
    }*/
 
  /*Function to find the height(depth) of the tree*/
  static int height(Node root)
  {
 
    // Initialising a variable to count the
    // height of tree
    Queue<Node> q=new Queue<Node>();
    q.Enqueue(root);
    int height = 0;
    while (q.Count>0) {
      int size = q.Count;
      for (int i = 0; i < size; i++) {
        Node temp = q.Peek();
        q.Dequeue();
        if (temp.left != null) {
          q.Enqueue(temp.left);
        }
        if (temp.right != null) {
          q.Enqueue(temp.right);
        }
      }
      height++;
    }
    return height;
  }
 
  // Driver program
  public static void Main()
  {
 
    // Let us create Binary Tree shown in above example
    Node root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
 
    root.left.left = new Node(4);
    root.left.right = new Node(5);
 
    Console.Write("Height(Depth) of tree is: " + height(root));
  }
}
 
// This code is contributed by poojaagarwal2.

Javascript

// JavaScript program for above approach
// a tree node
class Node{
    constructor(key){
        this.key = key;
        this.left = this.right = null;
    }   
}
 
// utility function to create a new node
function newNode(key){
    return new Node(key);
}
 
// function to find the  height of the tree
function height(root){
    // initialising a variable to count the
    // height of tree
    let q = [];
    q.push(root);
    let height = 0;
    while(q.length > 0){
        let size = q.length;
        for(let i = 0; i<size; i++){
            let temp =  q.shift();
            if(temp.left != null){
                q.push(temp.left);
            }
            if(temp.right != null){
                q.push(temp.right);
            }
        }
        height++;
    }
    return height;
}
 
// driver code
let root = newNode(1);
root.left = newNode(2);
root.right = newNode(3);
root.left.left = newNode(4);
root.left.right = newNode(5);
 
document.write("Height(Depth) of tree is: " + height(root));
 
// this code is contributed by Kirti Agarwal(kirtiagarwal23121999)

Output

Height(Depth) of tree is: 3

Time Complexity: O(N)
Auxiliary Space: O(N)

GeeksforGeeks

Improve

Previous Article

Binary Tree (Array implementation)

Insertion in a Binary Tree in level order

Similar Reads

Height and Depth of a node in a Binary Tree

Given a Binary Tree consisting of N nodes and a integer K, the task is to find the depth and height of the node with value K in the Binary Tree. The depth of a node is the number of edges present in path from the root node of a tree to that node.The height of a node is the number of edges present in the longest path connecting that node to a leaf n

Sum of nodes at maximum depth of a Binary Tree | Iterative Approach

Given a root node to a tree, find the sum of all the leaf nodes which are at maximum depth from the root node. Example: 1 / \ 2 3 / \ / \ 4 5 6 7 Input : root(of above tree) Output : 22 Explanation: Nodes at maximum depth are 4, 5, 6, 7. So, the sum of these nodes = 22 Approach: There exists a recursive approach to this problem. This can also be so

Sum of nodes at maximum depth of a Binary Tree | Set 2

Given a root node to a tree, find the sum of all the leaf nodes which are at maximum depth from root node. Example: 1 / \ 2 3 / \ / \ 4 5 6 7 Input : root(of above tree) Output : 22 Explanation: Nodes at maximum depth are: 4, 5, 6, 7. So, sum of these nodes = 22 In the previous article we discussed a recursive solution which first finds the maximum

Sum of nodes at maximum depth of a Binary Tree

Given a root node to a tree, find the sum of all the leaf nodes which are at maximum depth from root node. Example: 1 / \ 2 3 / \ / \ 4 5 6 7 Input : root(of above tree) Output : 22 Explanation: Nodes at maximum depth are: 4, 5, 6, 7. So, sum of these nodes = 22 While traversing the nodes compare the level of the node with max_level (Maximum level

Find Minimum Depth of a Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. For example, minimum depth of below Binary Tree is 2. Note that the path must end on a leaf node. For example, the minimum depth of below Binary Tree is also 2. 10 / 5 Recommended PracticeMi

Check if a given Binary Tree is height balanced like a Red-Black Tree

In a Red-Black Tree, the maximum height of a node is at most twice the minimum height (The four Red-Black tree properties make sure this is always followed). Given a Binary Search Tree, we need to check for following property. For every node, length of the longest leaf to node path has not more than twice the nodes on shortest path from node to lea

Maximum height of the binary search tree created from the given array

Given an array arr[] of N integers, the task is to make two binary search trees. One while traversing from the left side of the array and another while traversing from the right and find which tree has a greater height.Examples: Input: arr[] = {2, 1, 3, 4} Output: 0 BST starting from first index BST starting from last index 2 4 / \ / 1 3 3 \ / 4 1

Maximum height of an elevation possible such that adjacent matrix cells have a difference of at most height 1

Given a matrix mat][][] of size M x N which represents the topographic map of a region, and 0 denotes land and 1 denotes elevation, the task is to maximize the height in the matrix by assigning each cell a non-negative height such that the height of a land cell is 0 and two adjacent cells must have an absolute height difference of at most 1. Exampl

Calculate depth of a full Binary tree from Preorder

Given preorder of a binary tree, calculate its depth(or height) [starting from depth 0]. The preorder is given as a string with two possible characters. 'l' denotes the leaf'n' denotes internal node The given tree can be seen as a full binary tree where every node has 0 or two children. The two children of a node can 'n' or 'l' or mix of both. Exam

Replace node with depth in a binary tree

Given a binary tree, replace each node with its depth value. For example, consider the following tree. Root is at depth 0, change its value to 0 and next level nodes are at depth 1 and so on. 3 0 / \ / \ 2 5 == >; 1 1 / \ / \ 1 4 2 2 The idea is to traverse tree starting from root. While traversing pass depth of node as parameter. We can track d

Article Tags :

Practice Tags :