Title:

Diameter of a Binary Tree

Link to LeetCode:

https://leetcode.com/problems/diameter-of-binary-tree/

Specification:

Given a binary tree, you need to compute the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree.
This path may or may not pass through the root.
The length of path between two nodes is represented by the number of edges between them.

Examples:

Example 1:

Given the binary tree [1,2,3,4,5],
return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Initial Code and Signature: 

public class DiameterOfBinaryTree {
	public int diameterOfBinaryTree (TreeNode root)
	{ }
	}

Algorithm:

Recursive Version:

  1. Start from root
  2. Calculate longest left and right paths from the current node
  3. Update the "longest paths" if the sum of the longest paths from current node is greater than the sum of the "longest paths"
  4. Go to the next node
  5. Continue until all the nodes in the tree are visited
  6. Return sum of the "longest paths"
Calculate longest left and right paths from current node:
  1. Is the node a leaf?
  2. Yes: return [0,0]
  3. No: return [max of (longest left and right paths from left child) + 1 , max of (longest left and right paths from right child ) + 1]

Run-Time Analysis:

GitHub Project:

Code: 


/**
 * 
 * @author Mahsa Sadi
 * @since 2020-02-17 
 *
 */
public class DiameterOfBinaryTree {


	/**
	 * Problem: Diameter of a Binary Tree
	 * 
	 * 
	 * Description: Given a binary tree, you need to compute the length of the diameter of the tree. 
	 * The diameter of a binary tree is the length of the longest path between any two nodes in a tree. 
	 * This path may or may not pass through the root.
	 */

	/**
	 * Solution: 
	 * 1- Start from root
	 * 2- longest paths = [-1,-1]
	 * 3- Calculate farthest right and left paths from the current node
	 * 4- Update the longest paths if the sum of the farthest paths are longer than the sum of the longest paths 
	 * 5- Go to the next node
	 * 6- Continue until all the nodes are visited.
	 * 7- Return sum of the longest paths
	 * 
	 * 
	 * 
	 * Calculate farthest paths from current node:
	 * 1- Is the node a leaf?
	 * 	2-Yes: farthest path form node : [0,0]
	 *         3- Update longest path if this path is longer
	 * 2- No: 
	 *   2- Has left child?
	 *   	3- No: return [0, max of (farthest left and right paths from right child + 1)]
	 *     		 4- Update longest paths if this path is longer
	 *   2- Yes:
	 *   	3- Has right child?
	 *   		4- No: return [max of (farthest left and right paths from left child +1) , 0]
	 *          	5- Update longest paths if this path is longer
	 *      4- Yes: 
	 *      	5- return [max of (farthest path left and right from left child +1) , max of (farthest left and right path from right child + 1)]
	 *         	 	6- Update longest paths if this path is longer
	 * 

	 */


	private int longestPaths [] = {-1, -1};


	public int diameterOfBinaryTree (TreeNode root)
	{
		farthestPathFrom (root);
		return longestPaths [0] + longestPaths [1];
	}



	public int [] farthestPathFrom (TreeNode n)

	{   int farthestPaths [] = {-1, -1};


		if (n == null)
		{
			farthestPaths [0] = farthestPaths [1] = 0;
		}
	
	
		else if (isLeaf (n))
		{
			farthestPaths [0] = farthestPaths [1] = 0;
		}
	
		else 
		{
			int [] farthestPathsFromRight;
			int [] farthestPathsFromLeft;
	
			if (n.getLeftChild () == null )
			{
				farthestPaths [0] = 0;
				farthestPathsFromRight = farthestPathFrom (n.getRightChild ());
				farthestPaths [1] = Math.max (farthestPathsFromRight [0] + 1, farthestPathsFromRight [1] + 1);
				
			}
	
			else if (n.getRightChild () == null )
			{
				farthestPathsFromLeft = farthestPathFrom (n.getLeftChild ());
				farthestPaths [0] = Math.max (farthestPathsFromLeft [0] + 1 , farthestPathsFromLeft [1] + 1);
				farthestPaths [1] = 0;
			}
	
			else 
			{
				farthestPathsFromLeft = farthestPathFrom (n.getLeftChild ());
				farthestPathsFromRight = farthestPathFrom (n.getRightChild ());
	
				farthestPaths [0] = Math.max (farthestPathsFromLeft [0] + 1, farthestPathsFromLeft [1] + 1);
				farthestPaths [1] = Math.max (  farthestPathsFromRight [0] + 1, farthestPathsFromRight [1] + 1);
	
			}
	}


	
	if ( (farthestPaths [0] + farthestPaths [1]) > ( longestPaths [0] + longestPaths [1]))
		longestPaths = farthestPaths;

	return farthestPaths;
	}



	public boolean isLeaf (TreeNode n)
	{
		return n.getLeftChild() == null && n.getRightChild() == null;
	}


}