Practice › Trees
Diameter of a Binary Tree
Medium · Trees · Asked at Amazon, Google, Meta, Microsoft
The diameter is the number of edges on the longest path between any two nodes. Print it.
Input
First line: k. Second line: k values — the tree in level order, -1 means no node.
Output
The diameter.
Constraints
- 1 ≤ number of nodes ≤ 10^4
At each node, left height + right height is a candidate; compute heights in one DFS.
Example 1
Input
5 1 2 3 4 5
Output
3
Example 2
Input
2 1 2
Output
1
Hints
- The longest path "bends" at some highest node: it goes down the left subtree and down the right subtree.
- At each node, height(left) + height(right) edges is a candidate. Compute heights in one DFS and update a global best.
Approach
Run one post-order DFS that returns heights (counted in nodes). At every node, the longest path bending there has height(left) + height(right) edges. Keep the maximum over all nodes. The path doesn't have to pass through the root, which is why every node is checked. One DFS gives O(n).
Complexity: O(n) time · O(h) recursion depth
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *left = nullptr, *right = nullptr;
Node(long long v) : val(v) {}
};
// Build a tree from level order where -1 means "no node".
Node *readTree() {
int k;
cin >> k;
vector<long long> v(k);
for (auto &x : v) cin >> x;
if (k == 0 || v[0] == -1) return nullptr;
Node *root = new Node(v[0]);
queue<Node *> q;
q.push(root);
int i = 1;
while (!q.empty() && i < k) {
Node *cur = q.front();
q.pop();
if (i < k && v[i] != -1) q.push(cur->left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.push(cur->right = new Node(v[i]));
i++;
}
return root;
}
int best = 0;
int height(Node *node) {
if (!node) return 0;
int l = height(node->left), r = height(node->right);
best = max(best, l + r); // longest path bending at this node, in edges
return 1 + max(l, r);
}
int main() {
height(readTree());
cout << best << "\n";
return 0;
}Python solution
import sys
from collections import deque
sys.setrecursionlimit(100000)
class Node:
def __init__(self, val):
self.val, self.left, self.right = val, None, None
def read_tree():
"""Build a tree from level order where -1 means "no node"."""
data = list(map(int, sys.stdin.read().split()))
k, v = data[0], data[1 : data[0] + 1]
if not v or v[0] == -1:
return None
root = Node(v[0])
q, i = deque([root]), 1
while q and i < k:
cur = q.popleft()
if i < k and v[i] != -1:
cur.left = Node(v[i])
q.append(cur.left)
i += 1
if i < k and v[i] != -1:
cur.right = Node(v[i])
q.append(cur.right)
i += 1
return root
best = 0
def height(node):
global best
if node is None:
return 0
l, r = height(node.left), height(node.right)
best = max(best, l + r) # longest path bending at this node, in edges
return 1 + max(l, r)
height(read_tree())
print(best)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node left, right;
Node(long v) { val = v; }
}
// Build a tree from level order where -1 means "no node".
static Node readTree(Scanner sc) {
int k = sc.nextInt();
long[] v = new long[k];
for (int i = 0; i < k; i++) v[i] = sc.nextLong();
if (k == 0 || v[0] == -1) return null;
Node root = new Node(v[0]);
ArrayDeque<Node> q = new ArrayDeque<>();
q.add(root);
int i = 1;
while (!q.isEmpty() && i < k) {
Node cur = q.poll();
if (i < k && v[i] != -1) q.add(cur.left = new Node(v[i]));
i++;
if (i < k && v[i] != -1) q.add(cur.right = new Node(v[i]));
i++;
}
return root;
}
static int best = 0;
static int height(Node node) {
if (node == null) return 0;
int l = height(node.left), r = height(node.right);
best = Math.max(best, l + r); // longest path bending at this node, in edges
return 1 + Math.max(l, r);
}
public static void main(String[] args) {
height(readTree(new Scanner(System.in)));
System.out.println(best);
}
}Solve Diameter of a Binary Tree online · All practice problems