Sep 2, 2013

Find depth of the deepest odd level leaf node in a binary tree

Write a program to find maximum height of the odd level leaf node of a binary tree. The problem has been picked up from GeeksforGeeks

A quick solution will be to use the solution for finding the max depth of the tree and modifying it to calculate the depth using only the odd level leaf nodes.

public static int maxOddLeafHeight()
{
    return maxOddLeafHeight(root, 0);
}

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

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

    /*
     * if height of both the left and right child trees is odd return the
     * maximum height of the two
     */
    if (lh % 2 == 1 && rh % 2 == 1)
    {
        return lh > rh ? lh : rh;
    }
    else if (lh % 2 == 1 && rh % 2 == 0)
    {
        return lh;
    }
    else if (rh % 2 == 0 && rh % 2 == 1)
    {
        return rh;
    }
    else
    {
        return 0;
    }
}
After a little refactoring
public static int maxOddLeafHeight()
{
    return maxOddLeafHeight(root, 1);
}

private static int maxOddLeafHeight(Node node, int h)
{
    if (node.right == null && node.left == null)
    {
        return h % 2 == 0 ? 0 : h;
    }

    int lh = node.left != null ? maxOddLeafHeight(node.left, h + 1) : 0;
    int rh = node.right != null ? maxOddLeafHeight(node.right, h + 1) : 0;

    return lh > rh ? lh : rh;
}

The complete program and sample execution
package programs;

public class BST
{
    private static Node root = null;

    public static int maxOddLeafHeight()
    {
        return maxOddLeafHeight(root, 1);
    }

    private static int maxOddLeafHeight(Node node, int h)
    {
        if (node.right == null && node.left == null)
        {
            return h % 2 == 0 ? 0 : h;
        }

        int lh = node.left != null ? maxOddLeafHeight(node.left, h + 1) : 0;
        int rh = node.right != null ? maxOddLeafHeight(node.right, h + 1) : 0;

        return lh > rh ? lh : rh;
    }

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

    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(1);
        root.left = new Node(2);
        root.left.left = new Node(4);
        root.right = new Node(3);
        root.right.left = new Node(5);
        root.right.right = new Node(6);
        root.right.left.right = new Node(7);
        root.right.left.right.left = new Node(9);
        root.right.right.right = new Node(8);
        root.right.right.right.right = new Node(10);
        root.right.right.right.right.left = new Node(11);

        return root;
    }
}

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

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

Output

1 comment :

Shanthi Ganesan said...

Very good post thanks...

Post a Comment