Diameter of a Tree

Given the root of a binary tree, create a function diameterOfTree that determines and returns the length of the diameter of the tree, where the diameter of a tree is defined as the number of nodes along the longest path between any two nodes in the tree.

For example, given the following binary tree:

The diameter is 4, which is the length of the path [4, 2, 1, 3] or [5, 2, 1, 3].

Community solutions

💬 Community guidelines

Stay on topic. Use this section for submitting solutions and providing feedback to others.
Be inclusive. Exponent is a diverse community. Please respect others' opinions and beliefs.

How would you answer? Submit your response below and get feedback from the community.

Gabriele G.99

October 21, 2024

Without using a recursive approach, one can perform a post-order traversal by removing the parent nodes from the stack only if children were visited:

Python

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

    diameter = 0
    stack = deque([[root, False]]) # (node, visited)
    node_heights = {}

    while stack:
        curr_node, visited = stack[-1]
        
        if visited:
            height_left = node_heights.get(curr_node.left, 0)
            height_right = node_heights.get(curr_node.right, 0)
            
            diameter = max(diameter, height_left + height_right)
            node_heights[curr_node] = max(height_left, height_right) + 1
            stack.pop() # a node can be deleted if its leaves were visited
        else:
            stack[-1][1] = True
            if curr_node.left is not None:
                stack.append([curr_node.left, False])
            if curr_node.right is not None:
                stack.append([curr_node.right, False])

    return diameter

Tiago R.148

November 4, 2024

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function exploreSubtree(node) {
    let leftHeight = 0;
    let rightHeight = 0;
    let maxDiameter = 0;

    // visit left
    if (node.left) {
        const leftVisit = exploreSubtree(node.left);
        leftHeight = leftVisit.height + 1;
        maxDiameter = Math.max(maxDiameter, leftVisit.maxDiameter);
    }

    // visit right
    if (node.right) {
        const rightVisit = exploreSubtree(node.right);
        rightHeight = rightVisit.height + 1;
        maxDiameter = Math.max(maxDiameter, rightVisit.maxDiameter);
    }

    const height = Math.max(leftHeight, rightHeight);
    const diameter = leftHeight + rightHeight > 0 ? leftHeight + rightHeight + 1 : 0;
    maxDiameter = Math.max(maxDiameter, diameter);

    // calculate diameter
    return {
        height,
        maxDiameter,
    };
}

function diameterOfTree(root) {
    return root ? exploreSubtree(root).maxDiameter : 0;
}

Jeff S.

Member

161

January 22, 2025

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function diameterOfTree(root) {
    if (root === null || root.left === null & root.right === null) {
        return 0;
    }

    function countBranch(node, count) {
        if (node.left === null && node.right === null) {
            return count;
        }

        let left = node.left === null ? 0 : countBranch(node.left, count+1);
        let right = node.right === null ? 0 : countBranch(node.right, count+1);
        return left >= right ? left : right;
    }

    let left = root.left === null ? 0 : countBranch(root.left, 1);
    let right = root.right === null ? 0 : countBranch(root.right, 1);

    return left + right;
}

// debug your code below
const 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);

console.log("Diameter of the tree:", diameterOfTree(root)); // Should output the diameter

Matthew K.

Member

147

February 27, 2025

JavaScript

class Node {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

function diameterOfTree(root) {
    // your code goes here
    let maxPath = 0
    function helper(node) {
        if (!node || !node.data) return 0

        const left = helper(node.left)
        const right = helper(node.right)
        maxPath = Math.max(maxPath, left + right)
        return Math.max(left, right) + 1
    }
    helper(root)
    return maxPath
}

// debug your code below
const 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);

console.log("Diameter of the tree:", diameterOfTree(root)); // Should output the diameter

See community answers

Software Engineering Introduction

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

System Design Interviews

Overview

Networking & API Design

Scalable Systems

Databases

Distributed Systems

Real-time & Events: Mock Interviews

Media & Content Delivery: Mock Interviews

Async & Data Processing: Mock Interviews

Payments & Marketplaces: Mock Interviews

Distributed Infrastructure: Mock Interviews

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Software Engineering Introduction

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

System Design Interviews

Overview

Networking & API Design

Scalable Systems

Databases

Distributed Systems

Real-time & Events: Mock Interviews

Media & Content Delivery: Mock Interviews

Async & Data Processing: Mock Interviews

Payments & Marketplaces: Mock Interviews

Distributed Infrastructure: Mock Interviews

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Diameter of a Tree