Diameter of Binary Tree Editorial

Practice Problem Link: Diameter of Binary Tree

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a binary tree, return 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 of the tree. The length is the number of edges in the path. The path may or may not include the root node.

Naive Approach

Since the diameter of a tree is the maximum of the diameter of the left subtree, the diameter of the right subtree or the diameter of the current tree. The idea is to calculate the sum of the depth of the left and right subtree to get the diameter of the current tree and update the maximum value of diameter by the sum for each node recursively.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getDepth(Node *root) {
	if(root == NULL) {
		return 0;
	}
	int leftSubtreeDepth = getDepth(root->left);
	int rightSubtreeDepth = getDepth(root->right);
	return max(leftSubtreeDepth, rightSubtreeDepth) + 1;
}
int getDiameter(Node* root) {
	if(root == NULL) {
		return 0;
	}
	int leftSubtreeDiameter = getDiameter(root->left);
	int rightSubtreeDiameter = getDiameter(root->right);
	int diameter = getDepth(root->left) + getDepth(root->right);
	diameter = max(diameter, max(leftSubtreeDiameter, rightSubtreeDiameter));
	return diameter;
}

Java

/* This is the Node class definition

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

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	int getDepth(Node root) {
		if(root == null) {
			return 0;
		}
		int leftSubtreeDepth = getDepth(root.left);
		int rightSubtreeDepth = getDepth(root.right);
		return Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;
	}
	int getDiameter(Node root) {
		if(root == null) {
			return 0;
		}
		int leftSubtreeDiameter = getDiameter(root.left);
		int rightSubtreeDiameter = getDiameter(root.right);
		int diameter = getDepth(root.left) + getDepth(root.right);
		diameter = Math.max(diameter, Math.max(leftSubtreeDiameter, rightSubtreeDiameter));
		return diameter;
		}
}

Optimal Approach

The optimal approach is exactly the same as the naive approach but the calculation of depths of the subtrees and the maximum diameter is done simultaneously in a single function to optimize the time complexity.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the Node class definition

class Node {
public:
    Node* left;
    Node* right;
    int data;

    Node(int data) {
        this->left = NULL;
        this->right = NULL;
        this->data = data;
    }
};
*/
int getMaxDepth(Node* root, int &diameter) {
	if(root == NULL) {
		return 0;
	}
	int leftSubtreeDepth = getMaxDepth(root->left, diameter);
	int rightSubtreeDepth = getMaxDepth(root->right, diameter);
	diameter = max(diameter, leftSubtreeDepth + rightSubtreeDepth);
	return max(leftSubtreeDepth, rightSubtreeDepth) + 1;
}
int getDiameter(Node* root) {
	int diameter = 0;
    getMaxDepth(root, diameter);
	return diameter;
}

Java

/* This is the Node class definition

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

    Node(int data) {
        this.data = data;
    }
}
*/

class Solution {
	static int diameter;
	int getMaxDepth(Node root) {
		if(root == null) {
			return 0;
		}
		int leftSubtreeDepth = getMaxDepth(root.left);
		int rightSubtreeDepth = getMaxDepth(root.right);
		diameter = Math.max(diameter, leftSubtreeDepth + rightSubtreeDepth);
		return Math.max(leftSubtreeDepth, rightSubtreeDepth) + 1;
	}
	int getDiameter(Node root) {
    	diameter = 0;
		getMaxDepth(root);
		return diameter;
	}
}