Table of contents

Diameter of a Binary Tree

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

Input/Output Examples

Example 1:

  • Input:

    plaintext
          1
     / \
    2   3
   / \
  4   5

  • Output: 3

    • Explanation: The longest path is [4 -> 2 -> 1 -> 3], which has 3 edges.

Example 2:

  • Input:

    plaintext
            10
       /  \
     20    30
    / \
  40   50

  • Output: 4

    • Explanation: The longest path is [40 -> 20 -> 10 -> 30], which has 4 edges.

Approach to find the diameter of a Binary Tree

  1. Recursive Approach:
    • For each node, calculate the height of the left and right subtrees.
    • The diameter at that node will be the sum of the heights of the left and right subtrees (i.e., the longest path passing through that node).
    • Keep track of the maximum diameter encountered during the recursive traversal.
  2. Base Case: If the node is None (i.e., an empty tree), the height is -1 and the diameter is 0.
  3. Global variable: We maintain a global variable (or similar construct) to keep track of the maximum diameter encountered during the recursion.
  4. Return value: The final result will be the maximum diameter found during the recursion.

C++ Program to find the Diameter of a Binary Tree

cpp
#include <iostream>
using namespace std;

// A binary tree node
struct Node {
    int data;
    Node* left;
    Node* right;
    
    Node(int val) {
        data = val;
        left = right = NULL;
    }
};

// Function to calculate the height of the tree and update the diameter
int heightAndDiameter(Node* root, int &diameter) {
    if (root == NULL) {
        return 0; // Base case: height of empty tree is 0
    }

    int leftHeight = heightAndDiameter(root->left, diameter);
    int rightHeight = heightAndDiameter(root->right, diameter);

    // Update the diameter with the sum of left and right heights
    diameter = max(diameter, leftHeight + rightHeight);

    // Return the height of the tree rooted at this node
    return max(leftHeight, rightHeight) + 1;
}

// Function to find the diameter of the binary tree
int diameterOfBinaryTree(Node* root) {
    int diameter = 0; // Initialize the diameter
    heightAndDiameter(root, diameter); // Recursively calculate height and diameter
    return diameter;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    cout << "The diameter of the binary tree is: " << diameterOfBinaryTree(root) << endl;
    return 0;
}

Java Program to find the Diameter of a Binary Tree

java
// A binary tree node class
class Node {
    int data;
    Node left, right;
    
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;
    
    // Utility function to calculate height and update the diameter
    public int heightAndDiameter(Node root, int[] diameter) {
        if (root == null) {
            return 0; // Base case: height of empty tree is 0
        }

        int leftHeight = heightAndDiameter(root.left, diameter);
        int rightHeight = heightAndDiameter(root.right, diameter);

        // Update the diameter with the sum of left and right heights
        diameter[0] = Math.max(diameter[0], leftHeight + rightHeight);

        // Return the height of the tree rooted at this node
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // Function to find the diameter of the binary tree
    public int diameterOfBinaryTree(Node root) {
        int[] diameter = new int[1]; // Initialize diameter as 0
        heightAndDiameter(root, diameter);
        return diameter[0];
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        
        System.out.println("The diameter of the binary tree is: " + tree.diameterOfBinaryTree(tree.root));
    }
}

Python Program to find the Diameter of a Binary Tree

python
# A class that represents a node of a binary tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Function to calculate height and update the diameter
def height_and_diameter(root, diameter):
    if root is None:
        return 0  # Base case: height of empty tree is 0
    
    left_height = height_and_diameter(root.left, diameter)
    right_height = height_and_diameter(root.right, diameter)
    
    # Update the diameter with the sum of left and right heights
    diameter[0] = max(diameter[0], left_height + right_height)
    
    # Return the height of the tree rooted at this node
    return max(left_height, right_height) + 1

# Function to find the diameter of the binary tree
def diameter_of_binary_tree(root):
    diameter = [0]  # Initialize the diameter as a list to modify it within the recursive function
    height_and_diameter(root, diameter)
    return diameter[0]

# Example usage
if __name__ == "__main__":
    root = Node(1)
    root.left = Node(2)
    root.right = Node(3)
    root.left.left = Node(4)
    root.left.right = Node(5)
    
    print("The diameter of the binary tree is:", diameter_of_binary_tree(root))

Explanation of Code:

  1. Base Case: If the node is None (i.e., the tree is empty), the height of that subtree is 0, and the diameter does not change.
  2. Recursion:
    • The function calculates the height of the left and right subtrees.
    • The diameter at each node is the sum of the heights of the left and right subtrees.
    • The global diameter is updated during each recursive call if a larger path is found.
  3. Return Value: The function returns the maximum height of the subtree rooted at each node. The diameter is tracked using a global variable (or array) and updated whenever a longer path is found.

Time Complexity:

  • O(n): The function visits each node of the tree exactly once, where n is the number of nodes in the tree.

Space Complexity:

  • O(h): Where h is the height of the binary tree. The space complexity is due to the recursive stack used during the depth-first traversal. In the worst case, if the tree is skewed, the space complexity can be O(n).

DSA

Related Articles