A Developer's Diary

Aug 29, 2013

Find max height of a binary tree

Program for finding maximum depth or height of a binary tree

/**
     * find height of the tree recursively
     */
    public static int maxHeight()
    {
        return maxHeight(root, 0);
    }
 
    private static int maxHeight(Node node, int h)
    {
        if (node == null)
        {
            return h;
        }
 
        int lh = maxHeight(node.left, h + 1);
        int rh = maxHeight(node.right, h + 1);
 
        return (lh > rh) ? lh : rh;
    }

The complete program and sample run
package programs;

public class BST
{
    private static Node root = null;

    /**
     * find height of the tree recursively
     */
    public static int maxHeight()
    {
        return maxHeight(root, 0);
    }

    private static int maxHeight(Node node, int h)
    {
        if (node == null)
        {
            return h;
        }

        int lh = maxHeight(node.left, h + 1);
        int rh = maxHeight(node.right, h + 1);

        return (lh > rh) ? lh : rh;
    }

    public static void main(String[] args)
    {
        createTree();
        printTree();
        System.out.println("Height " + maxHeight());
    }

    private static void printTree()
    {
        print(root);
    }

    private static void print(Node node)
    {
        if (node != null)
        {
            print(node.left);
            System.out.print(node.data + " ");
            print(node.right);
        }
    }

    private static Node createTree()
    {
        root = new Node(50);
        root.left = new Node(40);
        root.left.left = new Node(30);
        root.left.right = new Node(45);
        root.left.left.left = new Node(25);
        root.left.left.left.left = new Node(20);
        root.left.left.left.left.left = new Node(15);

        root.right = new Node(70);
        root.right.left = new Node(60);
        root.right.right = new Node(90);
        root.right.right.left = new Node(80);
        root.right.right.left.right = new Node(85);
        return root;
    }
}

class Node
{
    Node left;
    Node right;
    int data;

    public Node(int num)
    {
        this.data = num;
    }
}

Output

3 comments :

anjani02 said...

Salesforce CPQ Course
Understand Salesforce Configure, Price, Quote processes to automate and optimize sales operations. Learn pricing rules, product bundles, and quote generation through live projects.

ONLINE IT GURU said...

"Join our power bi live training
to master interactive dashboards and real-time data analysis with expert guidance."

ONLINE IT GURU said...

Boost your career with our comprehensive sfdc developer course
designed to teach you Salesforce development from basics to advanced. Master Apex, Visualforce, and Lightning components to become a certified SFDC developer.

Post a Comment