Search⌘ K
Home
Courses
Data Structures for Coding Interviews in C#

Solution Review: Finding the Height of a Binary Tree

Explore how to determine the height of a binary tree by applying recursion to traverse left and right subtrees. Learn to implement a function that returns the maximum height plus one, handling null nodes correctly. This lesson helps you grasp the recursive strategy and analyze its linear time complexity for binary tree height calculation.

We'll cover the following...

Solution: Using recursion

C#
using System;
namespace chapter_6
{
    class Solution
    {
        static int findHeight(Node rootNode)
        {
            if (rootNode == null)
                return -1;
            else
            {
                // Find Height of left subtree and then right subtree
                // Return greater height value of left or right subtree (plus 1)
                int leftHeight = findHeight(rootNode.leftChild);
                int rightHeight = findHeight(rootNode.rightChild);
                if (leftHeight > rightHeight)
                    return leftHeight + 1;
                else
                    return rightHeight + 1;
            }
        }
        static void Main(string[] args)
        {
            BinarySearchTree BST = new BinarySearchTree(6);
            BST.insertBST(4);
            BST.insertBST(9);
            BST.insertBST(5);
            BST.insertBST(2);
            BST.insertBST(8);
            BST.insertBST(12);
            Console.WriteLine(findHeight(BST.getRoot()));
        }
    }
}

You should recursively find the heights of the left and right-subtrees. Here return -1 if the given node is null. Then, call the ...