Diameter of Binary Tree

Q: What is the time complexity of Diameter of Binary Tree?

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

EasyTree traversal

+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 has five nodes and four edges. It turns at the root: three edges down the left, 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 it gets only three edges.

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.

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 need not pass through the root. Every path has one highest node, where it turns, and the longest path turning at a node has its left height plus its right height in edges. One post-order pass computes every height from the bottom up and checks every turning point, in O(n).

Measure every pair of nodes

Correct, but does not finish on the largest tests

Intuition

Measure every pair of nodes. The parent of index i is (i-1)/2, rounded down, so the distance between indexes a and b is the number of times you replace the larger index with its parent before they meet. A larger index is never on a higher level, so it never climbs past the meeting point. For 9 and 2 in the first example: 9 to 4 to 1, 2 to 0, 1 to 0, four steps.

A full tree of 16383 nodes has about 1.3 × 10^8 pairs, each up to 26 steps: billions of steps for one answer.

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

Let height(c) count the nodes on the longest downward path from c, with 0 for an empty spot. The longest path turning at node i then has height(2*i+1) + height(2*i+2) edges, one for each node below the turn. Try every node as the turning point and keep the best. In the second example the 5 at index 1 has height 2 on each side, four edges, while the root gives only 3 + 0.

Each height call walks a whole subtree, and a node is walked again for every ancestor, so the work is O(n·h). With h ≤ 14 that is fast, but on a chain-shaped tree it becomes O(n²).

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 needs only its children's heights, the same two numbers the turning-point check uses. A post-order traversal finishes both children before their parent, so at each node you hold left and right: update the answer with left + right, and return 1 + max(left, right) to the parent.

In the first example the 7 returns 1, the 4 returns 2 and the 3 returns 3. The 6 returns 1, so at the root left + right = 3 + 1 = 4. Each node is visited once: O(n) time, and the recursion is O(h) deep.

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

Counting nodes instead of edges. The path 7, 4, 3, 8, 6 has five nodes but length 4.
Measuring only through the root. In the second example that gives three, and the answer is four.
Returning the diameter from the recursive call. The parent needs heights; keep the diameter in a separate variable.
Mixing height conventions. Heights that count nodes, with 0 for an empty spot, give left + right edges. Heights that count edges need -1 for an empty spot and left + right + 2. Mixing them is off by one or two.
Reading past the end. A leaf near the end of the array has child indexes past its last entry; treat them as empty spots.

Frequently asked questions3

What is the time complexity of Diameter of Binary Tree?

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

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

No. The longest path can sit 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.

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

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

def diameterOfBinaryTree(tree):
    # Write code here

Test #1

Test #2

Test #3

Argument

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

Expected Output

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 questions3

Similar problems