Binary Tree Traversal: Preorder, Inorder, Postorder, BFS

Arrays, linked lists, stacks and queues are linear: each element has at most one after it. A lot of data is not shaped like that: a company's managers and teams, folders inside folders, an expression such as (2 + 3) × 4. These are trees: one item at the top, every other item hanging below exactly one parent. In a binary tree each node has at most two children, a left and a right. It is the tree interviews ask about most, and the shape underneath the binary search tree, the heap and the trie.

Why a tree and not a list

Finding one item in a list of a million can take a million steps. A tree whose levels are full doubles at every level — 1, 2, 4, 8 nodes — so twenty levels already hold more than a million (2²⁰ = 1,048,576). Anything that walks one path from the root to a leaf then costs about 20 steps, as long as the tree stays bushy rather than stringy. That is why search trees, heaps and tries exist; and when the data is a hierarchy anyway, the tree is simply its honest shape.

The parts of a tree

Every example in this lesson uses the same seven-node tree:

This lesson counts height in edges, as textbooks do: a leaf has height 0 and an empty tree −1. Many problems, such as "maximum depth of a binary tree", count nodes instead and give this tree a depth of 4. Check the examples.

How a binary tree is stored

A node holds a value and two references, left and right, each pointing at a child or at nothing — a linked list with two "next" pointers. Problems hand you a tree as linked nodes, as a parent array or edge list (most of the catalogue, see below), or as a level-order listing with null for each missing child: [1, 2, 3, 4, 5, null, 6, null, null, 7] is the tree above. Nodes receive their children in the order they were created, so a queue builds it:

1. The first entry, 1, becomes the root and joins a queue. The listing goes level by level, so nodes receive their children in the order they were created: first in, first out.
2. Take 1 from the front of the queue: the next two entries, 2 and 3, become its left and right children and join the back of the queue.
3. Take 2 from the front of the queue: the next two entries, 4 and 5, become its left and right children and join the back of the queue.
4. Take 3: the next two entries are null and 6, so 3 has no left child, and 6 becomes its right child and joins the queue.
5. Take 4: the next two entries are both null, so 4 gets no children — it is a leaf — and nothing joins the queue.
6. Take 5: only one entry is left, 7, so 7 becomes its left child and joins the queue, and the listing ends there.
7. The listing has run out, so 6 and 7 never receive children: they are leaves. Every entry was read once and every node queued once, so building the tree takes O(n) time.

A tree with no gaps can even live in a plain array with no pointers at all: that is the heap's trick.

The four traversals

A traversal visits every node once, and choosing the right order is half of most tree problems. The three depth-first orders finish the left subtree, then the right, and differ only in when they visit the node: preorder before both subtrees, inorder between them, postorder after both. One walk round the tree gives all three:

1. Walk round the outside of the tree, starting at the root and keeping the tree on your left. You pass every node three times — on its left, underneath it, then on its right — and the three depth-first orders differ only in which pass writes it.
2. Start on the left of the root, 1. This is its first pass, so preorder writes 1 before anything else.
3. Down to 2, passing its left side: preorder writes 2. Its left subtree comes next.
4. Down to 4, a leaf. With no subtrees in the way, the walk rounds its left side, underside and right side in one go, so 4 joins all three orders.
5. Back up to 2 from its left subtree, passing underneath it: inorder writes 2. Its right subtree comes next.
6. Down to 5, passing its left side: preorder writes 5. Its left subtree comes next.
7. Down to 7, another leaf: it joins all three orders at once.
8. Back up to 5 from its left subtree. It has no right child, so the walk passes underneath it and straight up its right side: inorder and postorder both write 5.
9. Back up to 2 from its right subtree, passing its right side: both of its subtrees are finished, so postorder writes 2.
10. Back up to 1 from its left subtree, passing underneath it: inorder writes 1. Its right subtree comes next.
11. Down to 3, which has no left child, so the walk passes its left side and its underside at once: preorder and inorder both write 3.
12. Down to 6, another leaf: it joins all three orders at once.
13. Back up to 3 from its right subtree, passing its right side: both of its subtrees are finished, so postorder writes 3.
14. Back up to 1 from its right subtree, passing its right side: both of its subtrees are finished, so postorder writes 1.
15. Preorder (1 2 4 5 7 3 6) writes a node at its first pass, inorder (4 2 7 5 1 3 6) at the second and postorder (4 7 5 2 6 3 1) at the third. Each node is passed three times, so every traversal is O(n).

Level order is breadth-first, level by level. A queue does it, and the queue is what keeps the levels apart:

1. Level order starts with the root alone in a queue. Every step takes the node at the front, writes it down, and puts its children at the back.
2. Take 1 and write it; its children 2 and 3 join the back of the queue.
3. Take 2 and write it. At that moment the queue held exactly level 1: 2 and 3. Its children 4 and 5 join the back of the queue behind them, so no deeper node can come out first.
4. Take 3 and write it; its child 6 joins the back of the queue, behind the rest of level 1.
5. Take 4 and write it. At that moment the queue held exactly level 2: 4, 5 and 6. 4 is a leaf, so nothing joins.
6. Take 5 and write it; its child 7 joins the back of the queue, behind the rest of level 2.
7. Take 6 and write it; it is a leaf, so nothing joins.
8. Take 7, the last node: it is a leaf, so nothing joins, and the queue is empty. The order is [1, 2, 3, 4, 5, 6, 7], level by level; each node was queued and taken once, so it is O(n).

Use preorder when a node hands something down to its children or to copy a tree; inorder for a binary search tree's values in sorted order; postorder when a node's answer depends on its children's; level order for levels and the nearest node to the root.

Ask the children, combine the answers

Most tree problems are one pattern: ask each child's subtree for its answer, then combine the answers with the node's own value. Height, size, sums and leaf counts all have this shape.

1. To find a node's height, ask both children for theirs and add one to the larger. An empty child answers −1, so that a leaf comes out at 0. Nothing is known yet: the answers start at the bottom.
2. 4 is a leaf: both children are empty and answer −1, so height(4) = 1 + max(−1, −1) = 0. It hands 0 back to its parent.
3. 7 is a leaf too: height(7) = 0, ready for its parent.
4. 5 hears 0 from 7, and its empty right side answers −1: height(5) = 1 + max(0, −1) = 1.
5. 2 hears 0 from 4 and 1 from 5: height(2) = 1 + max(0, 1) = 2.
6. 6 is a leaf too: height(6) = 0, ready for its parent.
7. 3 hears 0 from 6, and its empty left side answers −1: height(3) = 1 + max(−1, 0) = 1.
8. 1 hears 2 from 2 and 1 from 3: height(1) = 1 + max(2, 1) = 3. That is the height of the whole tree, found after both children had answered: a postorder walk, O(n).

Why trust the recursive calls? Each is about a smaller tree, and the shrinking always ends at the empty tree, whose answer is written down directly. If every smaller tree gets the right answer, the combining line makes this one right too — a proof by induction, and the reason recursion and trees fit so well. So never trace every call: decide what the empty tree returns and how a node combines its children, and you are done. Answers that come from the children flow up as return values, in postorder; a node's depth comes from its parent, so it flows down as a parameter, in preorder.

The code

The program builds the example tree from its listing, prints the four traversals, and computes the height and the size by asking the children.

#include <algorithm>
#include <iostream>
#include <optional>
#include <queue>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left = nullptr;
    Node* right = nullptr;
    explicit Node(int v) : val(v) {}
};

// Builds a tree from its level-order listing; nullopt marks a missing child.
Node* build(const vector<optional<int>>& arr) {
    if (arr.empty() || !arr[0]) return nullptr;
    Node* root = new Node(*arr[0]);
    queue<Node*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < arr.size()) {
        Node* node = q.front(); q.pop();     // nodes get children in creation order
        if (arr[i]) { node->left = new Node(*arr[i]); q.push(node->left); }
        i++;
        if (i < arr.size() && arr[i]) { node->right = new Node(*arr[i]); q.push(node->right); }
        i++;
    }
    return root;
}

void preorder(Node* n, vector<int>& out) {
    if (!n) return;
    out.push_back(n->val);                   // the node first
    preorder(n->left, out);
    preorder(n->right, out);
}

void inorder(Node* n, vector<int>& out) {
    if (!n) return;
    inorder(n->left, out);
    out.push_back(n->val);                   // the node between its subtrees
    inorder(n->right, out);
}

void postorder(Node* n, vector<int>& out) {
    if (!n) return;
    postorder(n->left, out);
    postorder(n->right, out);
    out.push_back(n->val);                   // the node after both subtrees
}

vector<int> levelOrder(Node* root) {
    vector<int> out;
    queue<Node*> q;
    if (root) q.push(root);
    while (!q.empty()) {
        Node* n = q.front(); q.pop();
        out.push_back(n->val);
        if (n->left) q.push(n->left);        // children wait behind the rest of this level
        if (n->right) q.push(n->right);
    }
    return out;
}

// Ask the children, combine the answers.
int height(Node* n) { return n ? 1 + max(height(n->left), height(n->right)) : -1; }
int treeSize(Node* n) { return n ? 1 + treeSize(n->left) + treeSize(n->right) : 0; }

void print(const string& label, const vector<int>& values) {
    cout << label << ":";
    for (int v : values) cout << " " << v;
    cout << "\n";
}

int main() {
    Node* root = build({1, 2, 3, 4, 5, nullopt, 6, nullopt, nullopt, 7});
    vector<int> preList, inList, postList;
    preorder(root, preList);
    inorder(root, inList);
    postorder(root, postList);
    print("Preorder", preList);
    print("Inorder", inList);
    print("Postorder", postList);
    print("Level order", levelOrder(root));
    cout << "Height: " << height(root) << "\n";
    cout << "Size: " << treeSize(root) << "\n";
    return 0;
}

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    // Builds a tree from its level-order listing; null marks a missing child.
    static Node build(Integer[] arr) {
        if (arr.length == 0 || arr[0] == null) return null;
        Node root = new Node(arr[0]);
        Queue<Node> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < arr.length) {
            Node node = q.poll();                // nodes get children in creation order
            if (arr[i] != null) { node.left = new Node(arr[i]); q.add(node.left); }
            i++;
            if (i < arr.length && arr[i] != null) { node.right = new Node(arr[i]); q.add(node.right); }
            i++;
        }
        return root;
    }

    static void preorder(Node n, List<Integer> out) {
        if (n == null) return;
        out.add(n.val);                          // the node first
        preorder(n.left, out);
        preorder(n.right, out);
    }

    static void inorder(Node n, List<Integer> out) {
        if (n == null) return;
        inorder(n.left, out);
        out.add(n.val);                          // the node between its subtrees
        inorder(n.right, out);
    }

    static void postorder(Node n, List<Integer> out) {
        if (n == null) return;
        postorder(n.left, out);
        postorder(n.right, out);
        out.add(n.val);                          // the node after both subtrees
    }

    static List<Integer> levelOrder(Node root) {
        List<Integer> out = new ArrayList<>();
        Queue<Node> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            Node n = q.poll();
            out.add(n.val);
            if (n.left != null) q.add(n.left);   // children wait behind the rest of this level
            if (n.right != null) q.add(n.right);
        }
        return out;
    }

    // Ask the children, combine the answers.
    static int height(Node n) { return n == null ? -1 : 1 + Math.max(height(n.left), height(n.right)); }
    static int treeSize(Node n) { return n == null ? 0 : 1 + treeSize(n.left) + treeSize(n.right); }

    static void print(String label, List<Integer> values) {
        StringBuilder line = new StringBuilder(label + ":");
        for (int v : values) line.append(" ").append(v);
        System.out.println(line);
    }

    public static void main(String[] args) {
        Node root = build(new Integer[] {1, 2, 3, 4, 5, null, 6, null, null, 7});
        List<Integer> preList = new ArrayList<>(), inList = new ArrayList<>(), postList = new ArrayList<>();
        preorder(root, preList);
        inorder(root, inList);
        postorder(root, postList);
        print("Preorder", preList);
        print("Inorder", inList);
        print("Postorder", postList);
        print("Level order", levelOrder(root));
        System.out.println("Height: " + height(root));
        System.out.println("Size: " + treeSize(root));
    }
}

from collections import deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def build(arr):
    """Build a tree from its level-order listing; None marks a missing child."""
    if not arr or arr[0] is None:
        return None
    root = Node(arr[0])
    q = deque([root])
    i = 1
    while q and i < len(arr):
        node = q.popleft()                   # nodes get children in creation order
        if arr[i] is not None:
            node.left = Node(arr[i])
            q.append(node.left)
        i += 1
        if i < len(arr) and arr[i] is not None:
            node.right = Node(arr[i])
            q.append(node.right)
        i += 1
    return root


def preorder(n, out):
    if n is not None:
        out.append(n.val)                    # the node first
        preorder(n.left, out)
        preorder(n.right, out)


def inorder(n, out):
    if n is not None:
        inorder(n.left, out)
        out.append(n.val)                    # the node between its subtrees
        inorder(n.right, out)


def postorder(n, out):
    if n is not None:
        postorder(n.left, out)
        postorder(n.right, out)
        out.append(n.val)                    # the node after both subtrees


def level_order(root):
    out = []
    q = deque([root] if root is not None else [])
    while q:
        n = q.popleft()
        out.append(n.val)
        if n.left is not None:               # children wait behind the rest of this level
            q.append(n.left)
        if n.right is not None:
            q.append(n.right)
    return out


# Ask the children, combine the answers.
def height(n):
    return -1 if n is None else 1 + max(height(n.left), height(n.right))


def tree_size(n):
    return 0 if n is None else 1 + tree_size(n.left) + tree_size(n.right)


root = build([1, 2, 3, 4, 5, None, 6, None, None, 7])
pre_list, in_list, post_list = [], [], []
preorder(root, pre_list)
inorder(root, in_list)
postorder(root, post_list)
print("Preorder:", *pre_list)
print("Inorder:", *in_list)
print("Postorder:", *post_list)
print("Level order:", *level_order(root))
print("Height:", height(root))
print("Size:", tree_size(root))

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

// Builds a tree from its level-order listing; null marks a missing child.
function build(arr) {
  if (arr.length === 0 || arr[0] === null) return null;
  const root = new Node(arr[0]);
  const q = [root];
  let head = 0; // index of the queue's front: shift() would cost O(n)
  let i = 1;
  while (head < q.length && i < arr.length) {
    const node = q[head++]; // nodes get children in creation order
    if (arr[i] !== null) { node.left = new Node(arr[i]); q.push(node.left); }
    i++;
    if (i < arr.length && arr[i] !== null) { node.right = new Node(arr[i]); q.push(node.right); }
    i++;
  }
  return root;
}

function preorder(n, out) {
  if (n === null) return;
  out.push(n.val); // the node first
  preorder(n.left, out);
  preorder(n.right, out);
}

function inorder(n, out) {
  if (n === null) return;
  inorder(n.left, out);
  out.push(n.val); // the node between its subtrees
  inorder(n.right, out);
}

function postorder(n, out) {
  if (n === null) return;
  postorder(n.left, out);
  postorder(n.right, out);
  out.push(n.val); // the node after both subtrees
}

function levelOrder(root) {
  const out = [];
  const q = root === null ? [] : [root];
  for (let head = 0; head < q.length; head++) {
    const n = q[head];
    out.push(n.val);
    if (n.left !== null) q.push(n.left); // children wait behind the rest of this level
    if (n.right !== null) q.push(n.right);
  }
  return out;
}

// Ask the children, combine the answers.
const height = (n) => (n === null ? -1 : 1 + Math.max(height(n.left), height(n.right)));
const treeSize = (n) => (n === null ? 0 : 1 + treeSize(n.left) + treeSize(n.right));

const show = (label, values) => console.log(`${label}: ${values.join(" ")}`);

const root = build([1, 2, 3, 4, 5, null, 6, null, null, 7]);
const preList = [], inList = [], postList = [];
preorder(root, preList);
inorder(root, inList);
postorder(root, postList);
show("Preorder", preList);
show("Inorder", inList);
show("Postorder", postList);
show("Level order", levelOrder(root));
console.log(`Height: ${height(root)}`);
console.log(`Size: ${treeSize(root)}`);

Preorder: 1 2 4 5 7 3 6
Inorder: 4 2 7 5 1 3 6
Postorder: 4 7 5 2 6 3 1
Level order: 1 2 3 4 5 6 7
Height: 3
Size: 7

Traversals without recursion

Recursion keeps one call frame per node on the current path. On a chain of 100,000 nodes that is 100,000 frames: Python stops at 1,000 by default, and the other languages can run out of stack. Keep the stack yourself instead:

1. Start at the root and go left as far as possible, pushing 1, 2 and 4. The stack now holds exactly the nodes whose left subtree is still being visited — what the recursive calls would be holding.
2. Pop 4: its left subtree is finished, so visit it. It has no right child, so nothing is pushed.
3. Pop 2: its left subtree is finished, so visit it. Then go right to 5 and left again as far as possible, pushing 5 and 7.
4. Pop 7: its left subtree is finished, so visit it. It has no right child, so nothing is pushed.
5. Pop 5: its left subtree is finished, so visit it. It has no right child, so nothing is pushed.
6. Pop 1: its left subtree is finished, so visit it. Then go right to 3, which has no left child: push it.
7. Pop 3: its left subtree is finished, so visit it. Then go right to 6, which has no left child: push it.
8. Pop 6 and visit it. The stack is empty and there is no right subtree left: done, [4, 2, 7, 5, 1, 3, 6] — the same as the recursion, with a stack you control.

Preorder is the same loop, visiting each node as it is pushed; the binary search tree lesson's kthSmallest is this loop in all four languages. To get level order one level at a time, read the queue's length when a level starts and take exactly that many nodes.

Trees given as a parent array or an edge list

Most catalogue problems never hand you node objects. Count Nodes With the Highest Score gives parents, with −1 for the root; Minimum Fuel Cost to Report to the Capital gives roads. Build children lists in one pass and the pattern works unchanged:

1. parents[i] names the parent of node i, and −1 marks the root, 0. One pass adds each node to its parent's list (0 → 1, 2; 1 → 3, 4; 2 → 5; 4 → 6), and the tree is there to walk: no node objects needed.
2. Depth flows down: dfs(node, depth) hands depth + 1 to each child, so depth is a parameter, known before the children are visited. The deepest node, 6, sits at depth 3, the tree's height.
3. Size flows up: each call returns 1 plus its children's sizes, so size is a return value, known only once the children have answered. Node 1's subtree holds 4 nodes and the root's all 7.

From an undirected edge list, build adjacency lists and pass each call the node it came from, so it never walks back up — this is depth-first search on a graph without cycles. The program computes both directions in one walk:

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> children;
vector<int> depthOf, sizeOf;

// Depth flows down as a parameter; size flows up as the return value.
int dfs(int node, int depth) {
    depthOf[node] = depth;
    int size = 1;                                    // the node itself
    for (int child : children[node]) size += dfs(child, depth + 1);
    sizeOf[node] = size;
    return size;
}

int main() {
    vector<int> parents = {-1, 0, 0, 1, 1, 2, 4};
    int n = parents.size();
    children.assign(n, vector<int>());
    depthOf.assign(n, 0);
    sizeOf.assign(n, 0);
    int root = -1;
    for (int i = 0; i < n; i++) {
        if (parents[i] == -1) root = i;
        else children[parents[i]].push_back(i);      // one pass turns parents into children
    }
    dfs(root, 0);
    for (int i = 0; i < n; i++)
        cout << "node " << i << ": depth " << depthOf[i] << ", subtree size " << sizeOf[i] << "\n";
    cout << "Height: " << *max_element(depthOf.begin(), depthOf.end()) << "\n";
    return 0;
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> children = new ArrayList<>();
    static int[] depthOf, sizeOf;

    // Depth flows down as a parameter; size flows up as the return value.
    static int dfs(int node, int depth) {
        depthOf[node] = depth;
        int size = 1;                                // the node itself
        for (int child : children.get(node)) size += dfs(child, depth + 1);
        sizeOf[node] = size;
        return size;
    }

    public static void main(String[] args) {
        int[] parents = {-1, 0, 0, 1, 1, 2, 4};
        int n = parents.length;
        for (int i = 0; i < n; i++) children.add(new ArrayList<>());
        depthOf = new int[n];
        sizeOf = new int[n];
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) root = i;
            else children.get(parents[i]).add(i);    // one pass turns parents into children
        }
        dfs(root, 0);
        int height = 0;
        for (int i = 0; i < n; i++) {
            System.out.println("node " + i + ": depth " + depthOf[i] + ", subtree size " + sizeOf[i]);
            height = Math.max(height, depthOf[i]);
        }
        System.out.println("Height: " + height);
    }
}

parents = [-1, 0, 0, 1, 1, 2, 4]
n = len(parents)
children = [[] for _ in range(n)]
depth_of = [0] * n
size_of = [0] * n
root = -1
for i in range(n):
    if parents[i] == -1:
        root = i
    else:
        children[parents[i]].append(i)   # one pass turns parents into children


def dfs(node, depth):
    """Depth flows down as a parameter; size flows up as the return value."""
    depth_of[node] = depth
    size = 1                             # the node itself
    for child in children[node]:
        size += dfs(child, depth + 1)
    size_of[node] = size
    return size


dfs(root, 0)
for i in range(n):
    print(f"node {i}: depth {depth_of[i]}, subtree size {size_of[i]}")
print("Height:", max(depth_of))

const parents = [-1, 0, 0, 1, 1, 2, 4];
const n = parents.length;
const children = Array.from({ length: n }, () => []);
const depthOf = new Array(n).fill(0);
const sizeOf = new Array(n).fill(0);
let root = -1;
for (let i = 0; i < n; i++) {
  if (parents[i] === -1) root = i;
  else children[parents[i]].push(i); // one pass turns parents into children
}

// Depth flows down as a parameter; size flows up as the return value.
function dfs(node, depth) {
  depthOf[node] = depth;
  let size = 1; // the node itself
  for (const child of children[node]) size += dfs(child, depth + 1);
  sizeOf[node] = size;
  return size;
}

dfs(root, 0);
for (let i = 0; i < n; i++) console.log(`node ${i}: depth ${depthOf[i]}, subtree size ${sizeOf[i]}`);
console.log(`Height: ${Math.max(...depthOf)}`);

node 0: depth 0, subtree size 7
node 1: depth 1, subtree size 4
node 2: depth 1, subtree size 2
node 3: depth 2, subtree size 1
node 4: depth 2, subtree size 2
node 5: depth 2, subtree size 1
node 6: depth 3, subtree size 1
Height: 3

With sizes known, a node's score in Count Nodes With the Highest Score is the product of its children's sizes and n − size(node), the rest of the tree.

Full, complete, perfect and balanced trees

Interviewers use these four words precisely:

A balanced tree keeps walks cheap: at every node the two subtree heights differ by at most 1, which guarantees O(log n) height. The example tree is balanced. Checking it is an "ask the children" problem if each call returns its height with its verdict; calling height separately at every node costs up to O(n²).

Time and space complexity

A plain binary tree has no order, so finding a value means looking everywhere; the binary search tree adds the order and makes that O(h).

How to recognise a tree problem

• A hierarchy: a manager and employees, a capital and its roads, folders, a root.
• n nodes and n − 1 edges, connected, or a parent array: a tree, even unnamed.
• Something for every subtree — a size, a sum, a count: postorder.
• Something accumulated from the root down — a depth, a time: a parameter, preorder.
• Levels or the nearest node: level order, breadth-first search on a tree.

Common mistakes

• No empty-tree case: every recursive tree function starts with "if the node is empty, return …".
• Walking back to the parent in an undirected edge list: pass the parent in and skip it.
• Deep recursion on a chain: 10⁵ nodes can be one path; raise Python's limit or keep your own stack.
• Recomputing instead of returning: return everything a parent needs from one call.
• A slow queue: list.pop(0) and shift() move every element; use collections.deque or a head index.

Practice in this order

The catalogue gives its trees as parent arrays and edge lists, so these also practise the conversion above:

1. Reachable Nodes With Restrictions: a plain traversal that skips forbidden nodes.
2. Time Needed to Inform All Employees: a time passed down each path.
3. Count Nodes With the Highest Score: subtree sizes combined into a product.
4. Number of Nodes in the Sub-Tree With the Same Label: each child returns counts per letter.
5. Minimum Fuel Cost to Report to the Capital: subtree sizes decide the cars on each road.
6. Graph Valid Tree: n − 1 edges and connected.
7. Minimum Height Trees: peeling leaves level by level.
8. Longest Path With Different Adjacent Characters: each node combines its two best children.
9. Sum of Distances in Tree: one pass up, one down, an answer for every root.

The trees problem list has every tree problem in the catalogue. Next on the road is the binary search tree, which adds one ordering rule and turns an O(n) search into a walk down one path.