Diameter of Binary Tree

+10

You get a binary tree stored in the array tree in level order. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries. Return the diameter of the tree: the number of edges on the longest path between any two nodes. The path may pass through the root or stay inside one subtree.

Function

diameterOfBinaryTree(tree: integer-array) → integer

treeinteger-array: the binary tree in level order, with -1 for an empty spot
Returnsinteger: the number of edges on the longest path between two nodes

Constraints

1 ≤ tree.length ≤ 32767
Each tree[i] is -1 or a value with 0 ≤ tree[i] ≤ 1000.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries past the last node.
Both children of an empty spot are empty too, and the depth is at most 14.

Examples

Input: tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Output: 4
Explanation: The path 7, 4, 3, 8, 6 (indexes 9, 4, 1, 0, 2) holds five nodes joined by four edges. It turns at the root: three edges down the left side and one down the right.

Input: tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
Output: 4
Explanation: The path 3, 1, 5, 9, 4 has four edges and turns at the 5 at index 1. The root has no right child, so a path through the root gets only the three edges down its left side.

Input: tree = [6, -1, -1]
Output: 0
Explanation: A single node has no edges. The longest path is the node by itself, of length 0.

+12 hidden tests on Submit

Follow-up

How would you return the path itself, the node values from one end of the diameter to the other?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The longest path does not have to pass through the root, so measuring the two sides of the root is not enough. Every path does have one highest node, where it turns from going up to going down, and the longest path that turns at a node is its left height plus its right height. One post-order pass computes every height from the bottom up and checks every turning point on the way, in O(n).

Measure every pair of nodes

Correct, but does not finish on the largest tests

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2, so its parent sits at (i-1)/2, rounded down. A spot is real only if its index is inside the array and the value there is not -1. In [8, 3, 6, 1, 4, -1, -1, -1, -1, 7], the 7 at index 9 has its parent at index 4, and that 4 has its parent at index 1.

The diameter is the largest distance between two nodes, so you can measure every pair. To get the distance between indexes a and b, climb toward the root one step at a time until they meet, always from the larger index. A larger index is never on a higher level, so that step never passes the meeting point. The number of steps is the number of edges. For 9 and 2: the 9 climbs to 4 and then to 1, the 2 climbs to 0, and the 1 climbs to 0. Four steps.

This is correct but slow. The largest test is a full tree of 16383 nodes, which makes about 1.3 × 10^8 pairs, and each pair takes up to 26 steps. Billions of steps for one answer is far past the time limit.

Algorithm

Collect the indexes of all real nodes.
For every pair (a, b), set edges = 0 and repeat until a == b: replace the larger index with its parent and add 1 to edges.
Keep the largest edges you see and return it.

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

Measure both heights at every node

Intuition

Look at the longest path from its highest node, the node where it stops going up and starts going down. From there it goes as far down the left side as it can and as far down the right side as it can. Let height(c) count the nodes on the longest downward path from c, with 0 for an empty spot. Then the longest path that turns at node i has height(2*i+1) + height(2*i+2) edges, one edge for each of those nodes.

So try every node as the turning point and keep the best. In the second example the 5 at index 1 has height 2 on the left (1, 3) and 2 on the right (9, 4), a path of four edges. The root has height 3 on the left and 0 on the right, which gives only three.

Each call to height walks a whole subtree, and a node is walked again for every ancestor above it, so the work is O(n·h). With h ≤ 14 that is fast enough here, but on a chain-shaped pointer tree h can reach n and the same idea costs O(n²). The repeated height calls are the waste the last approach removes.

Algorithm

Write height(i): 0 for an empty spot, otherwise 1 + max(height(2*i+1), height(2*i+2)).
For every real node i, compute height(2*i+1) + height(2*i+2).
Return the largest of these sums.

def diameterOfBinaryTree(tree):
    n = len(tree)

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

One post-order pass over the heights

Intuition

A node's height depends only on the heights of its two children, and those are the same two numbers the turning-point check needs. So compute them once, from the bottom up. A post-order traversal finishes both children before their parent. At each node you then hold left and right: update the answer with left + right, and hand 1 + max(left, right) up to the parent.

In the first example the leaf 7 returns 1, the 4 above it returns 2, and the 3 returns 3, since its other child 1 has height 1. The 6 returns 1. At the root left + right = 3 + 1 = 4, the answer. The best any other node offers is the 3, with 1 + 2 = 3.

Each node is visited once, so the time is O(n), and the recursion is as deep as the tree, O(h), about one frame per level. The answer is kept in a variable outside the recursion, because what a call returns (a height) is not what you want at the end (a path length).

Algorithm

Set best = 0 and write height(i). For an empty spot, return 0.
Compute left = height(2*i+1) and right = height(2*i+2).
Set best to the larger of best and left + right.
Return 1 + max(left, right).
Call height(0) and return best.

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best

Pitfalls and edge cases

Most wrong answers count the wrong thing or measure at the wrong node.

Counting nodes instead of edges. The path 7, 4, 3, 8, 6 has five nodes and length 4, and a single node has diameter 0.
Measuring only through the root. In the second example the best path through the root has three edges, and the answer is four, turning at index 1.
Returning the diameter from the recursive call. The parent needs its children's heights to build longer paths; the diameter belongs in a separate variable.
Mixing two height conventions. With heights that count nodes and 0 for an empty spot, left + right is already the edge count. Heights that count edges need -1 for an empty spot and left + right + 2. Half of one and half of the other is off by one or two.
Reading past the end. A leaf near the end of the array can have child indexes past its last entry. Treat an index past the end as an empty spot.
Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

What is the time complexity of Diameter of Binary Tree?

The post-order solution visits each node once, so it runs in O(n) time with O(h) extra space for the recursion, where h is the height. Computing the heights separately at every node costs O(n·h), which becomes O(n²) on a tree shaped like a chain.

Does the diameter of a binary tree always pass through the root?

No. The longest path can sit entirely inside one subtree, for example when the root has one short branch and a deep, bushy subtree on the other side. That is why you check left + right at every node, not only at the root.

Is the diameter counted in nodes or in edges?

Here it is counted in edges, the links between consecutive nodes on the path, so a single node has diameter 0 and two connected nodes have diameter 1. Some books count nodes instead, which gives one more. Check which one a problem asks for before you add or drop the 1.

How do you find the diameter of a binary tree without recursion?

Visit the nodes in an order where every child comes before its parent. One way: push the root on a stack, pop nodes into a list while pushing their children, then walk that list backwards. Store each node's height in an array, read the two child heights at each node, and update the answer with their sum. The time stays O(n).

Python

def diameterOfBinaryTree(tree):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]

Expected

Diameter of Binary Tree

Function

Constraints

Examples

Hints

Solution

Measure every pair of nodes

Measure both heights at every node

One post-order pass over the heights

Pitfalls and edge cases

Frequently asked questions4

Similar problems