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

No comments :

Post a Comment