Profile a Binary Tree

Practice Exercise Intermediate Medium Binary Tree Tree

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement binary_tree_profile(level_order). The array uses complete-tree indexes (children of i are 2*i+1 and 2*i+2) and None for missing nodes. Ignore values whose parent is unreachable. Return [reachable_node_count, height_in_nodes, leaf_count].

Starter code

def binary_tree_profile(level_order):
    pass

Test cases

branching-tree

{
  "args": [
    [
      1,
      2,
      3,
      4,
      null,
      null,
      7
    ]
  ]
}

Expected: [5,3,2]

empty-tree

{
  "args": [
    []
  ]
}

Expected: [0,0,0]

Wizard outline

Step 1: Handle an absent root
Return the zero profile when the array is empty or its root slot is None. Every later traversal assumes a real root, so the boundary must exit first.
Step 2: Measure a single reachable root
Initialize a BFS frontier at level one and count a root with no children as one leaf. A single node establishes the starting values for count, height, and leaves.
Step 3: Enqueue only reachable children
Compute complete-tree child indexes and carry each reachable child at the next level. Adding children through the current reachable parent naturally ignores orphaned array values.

Footguns and prerequisites

Counting every non-None array value includes orphaned nodes below a missing parent.
Height measured in nodes differs by one from height measured in edges.
trees and graphs

Reviewed references

Python collections.deque

Recommended approach and implementation

Breadth-first traverse reachable complete-tree indexes while tracking each node level and whether it has present children.

Why it works: Only children of visited nodes enter the queue, so every and only reachable node is counted. The maximum queued level is the height, and nodes with no queued children are exactly the leaves.

from collections import deque

def binary_tree_profile(level_order):
    if not level_order or level_order[0] is None:
        return [0, 0, 0]
    queue = deque([(0, 1)])
    count = 0
    height = 0
    leaves = 0
    while queue:
        index, level = queue.popleft()
        count += 1
        height = max(height, level)
        children = [child for child in (2 * index + 1, 2 * index + 2) if child < len(level_order) and level_order[child] is not None]
        if not children:
            leaves += 1
        for child in children:
            queue.append((child, level + 1))
    return [count, height, leaves]