Jobs

Interviews

Discussions

Diameter of Binary Tree

Easy

Google

7 views

Topics:

TreesRecursion

Given the root of 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 in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

For example:

Consider the following binary tree:

The diameter of this tree is 3, which corresponds to the path [4,2,1,3] or [5,2,1,3].

As another example, consider the following binary tree:

   1
  / \
 2   3

The diameter of this tree is 2 because the longest path goes from one of the leaves, to the root, and then to the other leaf. Note that we want to return the number of edges and not nodes.

Write a function to calculate the diameter of a given binary tree.

Diameter of Binary Tree

Easy

Google

7 views

Topics:

TreesRecursion

Given the root of 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 in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

For example:

Consider the following binary tree:

The diameter of this tree is 3, which corresponds to the path [4,2,1,3] or [5,2,1,3].

As another example, consider the following binary tree:

   1
  / \
 2   3

The diameter of this tree is 2 because the longest path goes from one of the leaves, to the root, and then to the other leaf. Note that we want to return the number of edges and not nodes.

Write a function to calculate the diameter of a given binary tree.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the binary tree? Can the values be negative?
Can the tree be empty? If so, what should I return?
By 'diameter', do you mean the longest path (number of edges) between any two nodes in the tree, regardless of whether that path passes through the root?
Are the node values relevant to calculating the diameter, or is it purely based on the structure of the tree?
Is the input always a valid binary tree, or should I handle cases where it might not be (e.g., cycles, disconnected nodes)?

Brute Force Solution

Approach

The diameter of a tree is the longest path between any two nodes in the tree. A brute force approach involves checking every possible path to find the longest one. We essentially explore every single possible route through the tree.

Here's how the algorithm would work step-by-step:

For every node in the tree, consider it as a potential 'middle' point of the longest path.
From that 'middle' node, find the longest path going down its left side.
Also from that 'middle' node, find the longest path going down its right side.
Add the lengths of those two paths together. This is the length of a path going through that 'middle' node.
Repeat this process for every single node in the tree, treating each one as the potential 'middle' point.
Compare all the path lengths you've calculated. The biggest path length is the diameter of the tree.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def height_of_binary_tree(node):
    if node is None:
        return 0
    left_height = height_of_binary_tree(node.left)
    right_height = height_of_binary_tree(node.right)
    return max(left_height, right_height) + 1

def diameter_of_binary_tree_brute_force(root):
    if root is None:
        return 0

    # Calculate diameter with current node as root
    left_tree_height = height_of_binary_tree(root.left)

    right_tree_height = height_of_binary_tree(root.right)

    diameter_with_root = left_tree_height + right_tree_height

    # Recursively calculate diameter of left subtree
    left_diameter = diameter_of_binary_tree_brute_force(root.left)

    # Recursively calculate diameter of right subtree
    right_diameter = diameter_of_binary_tree_brute_force(root.right)

    # Return the maximum of the three diameters
    return max(diameter_with_root, max(left_diameter, right_diameter))

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each node in the tree (n nodes). For each node, it calculates the height of its left and right subtrees using a recursive height calculation. The height calculation itself takes O(n) time in the worst case (e.g., a skewed tree). Since this height calculation is performed for each of the n nodes, the overall time complexity is O(n * n), which simplifies to O(n²). The dominant operation is recalculating subtree heights repeatedly for each node.

Space Complexity

O(N) – The brute force approach described involves recursively calculating the longest path from each node. In the worst-case scenario (e.g., a skewed tree), the recursion depth could be equal to the number of nodes in the tree, N. Each recursive call adds a new frame to the call stack, consuming memory. Therefore, the auxiliary space complexity is determined by the maximum depth of the recursion stack, which is O(N).

Optimal Solution

Approach

The diameter of a binary tree is the longest path between any two nodes in the tree. The trick is to calculate the longest path passing through each node while also calculating the height of each node during a single exploration of the tree.

Here's how the algorithm would work step-by-step:

Imagine you're exploring the tree, starting from the very bottom.
For each node you visit, determine the height of its left and right sides.
Also, at each node, calculate the longest path that goes through that node by adding the left height, right height, and 2.
Keep track of the biggest path you find as you explore. That's potentially the diameter.
To figure out the height for the parent nodes, add 1 to the maximum height from the children nodes.
As you move upwards and outwards, remember that each node is an opportunity to discover a new biggest path, which also informs parent height calculations. The global biggest path is the final result.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root):
    longest_path = 0

    def depth_first_search(node):
        nonlocal longest_path

        # Base case: empty node has height 0
        if not node:
            return 0

        left_height = depth_first_search(node.left)
        right_height = depth_first_search(node.right)

        # Update the diameter if needed.
        longest_path = max(longest_path, left_height + right_height)

        # The height of the current node
        # is max child height + 1.
        return max(left_height, right_height) + 1

    depth_first_search(root)

    return longest_path

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary tree exactly once. At each node, it performs a constant amount of work: calculating the heights of the left and right subtrees and updating the diameter. Therefore, the time complexity is directly proportional to the number of nodes in the tree, n. This single traversal ensures all height and path calculations are performed efficiently, resulting in O(n) time.

Space Complexity

O(N) – The space complexity is determined by the recursion stack. In the worst-case scenario, where the binary tree is skewed (either left-skewed or right-skewed), the recursion depth can reach N, where N is the number of nodes in the tree. Each recursive call adds a new frame to the stack, consuming memory. Therefore, the auxiliary space used is proportional to the height of the tree, which in the worst case is N.

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 as the diameter of an empty tree is defined as zero.
Tree with only one node	Return 0, as the diameter of a single-node tree is zero since there are no paths.
Tree with only left children (left-skewed)	The algorithm correctly calculates the height of the left subtree which will be the diameter.
Tree with only right children (right-skewed)	The algorithm correctly calculates the height of the right subtree which will be the diameter.
Balanced tree with many nodes (scalability)	Ensure recursive calls don't exceed stack limits by using an iterative solution or tail-call optimization if the language supports it.
Tree with negative node values (if applicable, based on the problem's extended context/allowed values)	Node values are irrelevant to diameter calculation; the algorithm works based on node connections, not values.
Integer overflow when calculating the height of subtrees (large tree)	Use a data type with a larger range (e.g., long) if the tree's height might cause an integer overflow.
Tree where the diameter path does not pass through the root	The algorithm must correctly consider paths within subtrees, not just paths originating from the root node.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the binary tree? Can the values be negative?
Can the tree be empty? If so, what should I return?
By 'diameter', do you mean the longest path (number of edges) between any two nodes in the tree, regardless of whether that path passes through the root?
Are the node values relevant to calculating the diameter, or is it purely based on the structure of the tree?
Is the input always a valid binary tree, or should I handle cases where it might not be (e.g., cycles, disconnected nodes)?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

For every node in the tree, consider it as a potential 'middle' point of the longest path.
From that 'middle' node, find the longest path going down its left side.
Also from that 'middle' node, find the longest path going down its right side.
Add the lengths of those two paths together. This is the length of a path going through that 'middle' node.
Repeat this process for every single node in the tree, treating each one as the potential 'middle' point.
Compare all the path lengths you've calculated. The biggest path length is the diameter of the tree.

Code Implementation

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def height_of_binary_tree(node):
    if node is None:
        return 0
    left_height = height_of_binary_tree(node.left)
    right_height = height_of_binary_tree(node.right)
    return max(left_height, right_height) + 1

def diameter_of_binary_tree_brute_force(root):
    if root is None:
        return 0

    # Calculate diameter with current node as root
    left_tree_height = height_of_binary_tree(root.left)

    right_tree_height = height_of_binary_tree(root.right)

    diameter_with_root = left_tree_height + right_tree_height

    # Recursively calculate diameter of left subtree
    left_diameter = diameter_of_binary_tree_brute_force(root.left)

    # Recursively calculate diameter of right subtree
    right_diameter = diameter_of_binary_tree_brute_force(root.right)

    # Return the maximum of the three diameters
    return max(diameter_with_root, max(left_diameter, right_diameter))

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're exploring the tree, starting from the very bottom.
For each node you visit, determine the height of its left and right sides.
Also, at each node, calculate the longest path that goes through that node by adding the left height, right height, and 2.
Keep track of the biggest path you find as you explore. That's potentially the diameter.
To figure out the height for the parent nodes, add 1 to the maximum height from the children nodes.
As you move upwards and outwards, remember that each node is an opportunity to discover a new biggest path, which also informs parent height calculations. The global biggest path is the final result.

Code Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def diameter_of_binary_tree(root):
    longest_path = 0

    def depth_first_search(node):
        nonlocal longest_path

        # Base case: empty node has height 0
        if not node:
            return 0

        left_height = depth_first_search(node.left)
        right_height = depth_first_search(node.right)

        # Update the diameter if needed.
        longest_path = max(longest_path, left_height + right_height)

        # The height of the current node
        # is max child height + 1.
        return max(left_height, right_height) + 1

    depth_first_search(root)

    return longest_path

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty tree	Return 0 as the diameter of an empty tree is defined as zero.
Tree with only one node	Return 0, as the diameter of a single-node tree is zero since there are no paths.
Tree with only left children (left-skewed)	The algorithm correctly calculates the height of the left subtree which will be the diameter.
Tree with only right children (right-skewed)	The algorithm correctly calculates the height of the right subtree which will be the diameter.
Balanced tree with many nodes (scalability)	Ensure recursive calls don't exceed stack limits by using an iterative solution or tail-call optimization if the language supports it.
Tree with negative node values (if applicable, based on the problem's extended context/allowed values)	Node values are irrelevant to diameter calculation; the algorithm works based on node connections, not values.
Integer overflow when calculating the height of subtrees (large tree)	Use a data type with a larger range (e.g., long) if the tree's height might cause an integer overflow.
Tree where the diameter path does not pass through the root	The algorithm must correctly consider paths within subtrees, not just paths originating from the root node.