Diameter of a binary tree

Before discussing the current problem let me give brief introduction of binary trees and the basic interface and classes Iam using for coding Diameter of a Binary tree.

Binary Tree

A binary tree is made of nodes, where each node contains a “left” pointer, a “right” pointer, in additional a “parent” pointer and a data element. The “root” pointer points to the topmost node in the tree.  The left and right pointers recursively point to smaller “subtrees” on either side. A null pointer represents a binary tree with no elements — the empty tree.

The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

Class for Node is as follows:

package ds;

public class Node
{
    Node left;
    Node right;
    Node parent;
    int data;
}

Interface for a Tree is as follows:

package ds;

public interface Tree
{
    public Node search(int data);
}

Class for Binary tree which has create method, add method, search method and print method is as follows:

package ds;

import java.util.LinkedList;

public class BinaryTree implements Tree
{
    public static final String LEFT = "LEFT";
    public static final String RIGHT = "RIGHT";
    private Node root;

    public BinaryTree()
    {
    }

    public void create(int currentData)
    {
        if (root == null)
        {
            root = new Node();
        }

        root.data = currentData;
    }

    public void add(Node node, int currentData, String currentPosition)
    {
        if (node == null)
        {
            return;
        }

        Node currentNode = new Node();
        currentNode.data = currentData;

        if (LEFT.equals(currentPosition))
        {
            node.left = currentNode;
        }
        else if (RIGHT.equals(currentPosition))
        {
            node.right = currentNode;
        }
    }

    public Node search(int searchData)
    {
        if (root == null)
        {
            return null;
        }

        return search(searchData, root);
    }

    private Node search(int searchData, Node node)
    {
        if (node == null)
        {
            return null;
        }

        // Level order traversal to return the node
        LinkedList queueList = new LinkedList();
        queueList.add(node);

        Node currNode = null;

        while (!queueList.isEmpty())
        {
            currNode = (Node) queueList.removeFirst();

            if (currNode.data == searchData)
            {
                break;
            }
            else
            {
                if (currNode.left != null)
                {
                    queueList.add(currNode.left);
                }

                if (currNode.right != null)
                {
                    queueList.add(currNode.right);
                }
            }
        }

        return currNode;
    }

    public void printLevelOrder()
    {
        printLevelOrder(root);
        System.out.println();
    }

    public void printLevelOrder(Node node)
    {
        if (node == null)
        {
            return;
        }

        LinkedList queueList = new LinkedList();
        queueList.add(node);

        Node currNode = null;

        while (!queueList.isEmpty())
        {
            currNode = (Node) queueList.removeFirst();
            System.out.print(currNode.data + "    ");

            if (currNode.left != null)
            {
                queueList.add(currNode.left);
            }

            if (currNode.right != null)
            {
                queueList.add(currNode.right);
            }
        }
        System.out.println();
    }

    public void printInorder()
    {
        printInorder(root);
        System.out.println();
    }

    public void printInorder(Node node)
    {
        if(node == null)
        {
            return;
        }

        printInorder(node.left);
        System.out.print(node.data+"    ");
        printInorder(node.right);
    }

    public void printPreorder()
    {
        printPreorder(root);
        System.out.println();
    }

    public void printPreorder(Node node)
    {
        if(node == null)
        {
            return;
        }

        System.out.print(node.data+"    ");
        printPreorder(node.left);
        printPreorder(node.right);
    }

    public void printPostorder()
    {
        printPostorder(root);
        System.out.println();
    }

    public void printPostorder(Node node)
    {
        if(node == null)
        {
            return;
        }

        printPostorder(node.left);
        printPostorder(node.right);
        System.out.print(node.data+"    ");
    }

}

Diameter of a binary tree

Diameter of a Tree is defined as the number of nodes on the longest path between two leaves in the tree.

Have a look at the following figures:

In the above first figure the longest path between the leaves is through the root. And in the second figure the longest path between the leaves is in the left subtree of the root.

Hence the diameter of a binary tree T will be the largest of the following quantities:

  • the diameter of T’s left subtree
  • the diameter of T’s right subtree
  • the longest path between leaves that goes through the root of T (this can be computed from the heights of the subtrees of T)

Dry run for the following example:

Consider following binary tree:

At every node its left height, right height, left diameter and right diameter are presented:



Therefore for the root node, diameter is maximum of left diameter: 5, right diameter: 3, left height+ right height+1: 4+2+1. Here its 7.

The code for the above problem is as follows:

package ds;

public class DiameterOfTree
{
    public DiameterOfTree()
    {
    }

    public int diameterOfBinaryTree(Node node)
    {
        if (node == null)
        {
            return 0;
        }

        int leftHeight = heightOfBinaryTree(node.left);
        int rightHeight = heightOfBinaryTree(node.right);

        int leftDiameter = diameterOfBinaryTree(node.left);
        int rightDiameter = diameterOfBinaryTree(node.right);

        return Math.max(leftHeight + rightHeight + 1,
            Math.max(leftDiameter, rightDiameter));
    }

    public int heightOfBinaryTree(Node node)
    {
        if (node == null)
        {
            return 0;
        }
        else
        {
            return 1 +
            Math.max(heightOfBinaryTree(node.left),
                heightOfBinaryTree(node.right));
        }
    }

    public static void main(String[] args)
    {
        /*
        Constructing following tree
                        1
                    2         3
                4       5  6     7
            8       9
                 10     11
                                                        */
        BinaryTree binaryTree = new BinaryTree();

        binaryTree.create(1);

        Node root = binaryTree.search(1);
        binaryTree.add(root, 2, BinaryTree.LEFT);
        binaryTree.add(root, 3, BinaryTree.RIGHT);
        binaryTree.add(binaryTree.search(2), 4, BinaryTree.LEFT);
        binaryTree.add(binaryTree.search(2), 5, BinaryTree.RIGHT);
        binaryTree.add(binaryTree.search(3), 6, BinaryTree.LEFT);
        binaryTree.add(binaryTree.search(3), 7, BinaryTree.RIGHT);
        binaryTree.add(binaryTree.search(4), 8, BinaryTree.LEFT);
        binaryTree.add(binaryTree.search(4), 9, BinaryTree.RIGHT);
        binaryTree.add(binaryTree.search(9), 10, BinaryTree.LEFT);
        binaryTree.add(binaryTree.search(9), 11, BinaryTree.RIGHT);
        System.out.println("Binary Tree in level order is .... ");
        binaryTree.printLevelOrder();

        DiameterOfTree diaTree = new DiameterOfTree();
        System.out.println("Diameter is ....  " +
            diaTree.diameterOfBinaryTree(root));
    }
}

References

http://www.cs.duke.edu/courses/spring00/cps100/assign/trees/diameter.html

Please write comments if you find any of the above algorithms or codes incorrect, or find better ways to solve the same problem.

About these ads

14 Responses to Diameter of a binary tree

  1. [...] Implementation for Node, Tree, BinaryTree can be obtained from my previous post. [...]

  2. [...] Implementation for Node, Tree, BinaryTree can be obtained from my previous post. [...]

  3. PiterJankovich says:

    My name is Piter Jankovich. oOnly want to tell, that your blog is really cool
    And want to ask you: is this blog your hobby?
    P.S. Sorry for my bad english

  4. Fred says:

    Shouldn’t line 22:

    … leftHeight + rightHeight + 1,

    be:

    … lh + rh + 2,

    ? After all, there’s an edge, counting for 1, from us to both the left and right child nodes, for a total of 2. And we’re counting the dist from the tip of one to the tip of the other. It’s not a mere +1 for our own, single-level of additional height.

    Also, take eg leftHeight. You’re not distinguishing between the left child having no children (returning height 0), and /there being no left child/. You need to do the null test before calling height, and not add 1 if there is no child. The same of course for the right child.

    • Narayana says:

      Hi, Yes, I thought so too. But look at the definition of diameter. It is the number of nodes, not number of edges.

  5. [...] The busiest day of the year was April 5th with 331 views. The most popular post that day was Diameter of a binary tree. [...]

  6. Robert says:

    I think that instead of leftHeight + rightHeight + 1 there should be leftHeight + rightHeight. Correct me if I’m wrong

  7. vaibhav says:

    If we assume the height at node level is 1, then it should be (leftHeight + rightHeight – 1). Please let me know if I’m wrong.

  8. vaibhav says:

    height at root level is 1, not node.

  9. AT says:

    While I agree with your solution, I am having hard find figuring out why my solution might be incorrect. Appreciate your comments.

    As I see, we can maintain a max_sum variable and count the height of the left subtree (lh), height of right subtree (rh) and update the max_sum if lh + rh + 1 is its greater. We calculate this sum at each of the nodes in the tree.

    From your solution, ultimately the diameters will be calculated based on heights of the left and right subtrees at some point of time in the code.

  10. Aleksey O. says:

    As I see the mentioned algo is correct but takes O(n^2). I suppose O(n) algorithm is possible here. Just modify the main function to calculate both diameter and height.

  11. Snehal Masne says:

    There are three cases to consider when trying to find the longest path between two nodes in a binary tree (diameter):

    The longest path passes through the root,
    The longest path is entirely contained in the left sub-tree,
    The longest path is entirely contained in the right sub-tree.
    The longest path through the root is simply the sum of the heights of the left and right sub-trees + 1 (for the root node), and the other two can be found recursively:

    public static int getDiameter(BinaryTreeNode root) {
    if (root == null)
    return 0;

    int rootDiameter = getHeight(root.getLeft()) + getHeight(root.getRight()) + 1;
    int leftDiameter = getDiameter(root.getLeft());
    int rightDiameter = getDiameter(root.getRight());

    return Math.max(rootDiameter, Math.max(leftDiameter, rightDiameter));
    }

    public static int getHeight(BinaryTreeNode root) {
    if (root == null)
    return 0;

    return Math.max(getHeight(root.getLeft()), getHeight(root.getRight())) + 1;
    }

  12. Hey! Quick question that’s totally off topic. Do you know how to
    make your site mobile friendly? My site looks weird when browsing from my apple iphone.
    I’m trying to find a theme or plugin that might be able to
    resolve this issue. If you have any recommendations, please share.
    Appreciate it!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 60 other followers

%d bloggers like this: