Tree Data Structure Basics: Root, Leaf, Depth and Height

Folders on a disk, the elements of a web page, an org chart, the parse of an expression: all of them are trees. Before binary search trees, heaps and tries, there is a small vocabulary that every tree question assumes you know, and two words, depth and height, that candidates mix up more than any others. This is that vocabulary, with code that checks each definition.

The problem it solves

Lists and arrays model sequences: one thing after another. A lot of data is not a sequence but a hierarchy, where each item belongs to exactly one parent and may contain many children. A tree models that directly, and it gives you a path from the top to any item whose length is the depth. When the tree is kept balanced, that depth grows like log n instead of n, which is where the speed of binary search trees, heaps and database indexes comes from.

The intuition

The words, defined once:

• Node: one item. Edge: the link between a parent and a child.
• Root: the single node with no parent. Every other node has exactly one parent.
• Child, sibling, leaf: a node's children hang below it; siblings share a parent; a leaf has no children. An internal node has at least one.
• Ancestor, descendant, subtree: everything on the path up to the root, everything below a node, and a node together with all its descendants.
• Depth of a node: edges from the root down to it. The root has depth 0.
• Height of a node: edges on the longest path from it down to a leaf. A leaf has height 0, and the height of the tree is the height of its root, which equals the greatest depth of any node.

Depth looks up, height looks down. Watch the convention, though: some problems, such as "maximum depth of a binary tree", count nodes instead of edges, so a single node has depth 1. Ask which one the interviewer means.

Two facts follow from "one parent each". A tree with n nodes has exactly n - 1 edges, one per non-root node. And there are no cycles: following parent links from any node always ends at the root. Drop the one-parent rule and you have a general graph; restrict every node to at most two children and you have one of the kinds of binary tree.

Watch it run

The animation draws the lesson's folder tree: home, with docs and photos inside it, and cv.pdf inside docs. One node sits at the top with nothing above it: that is the root. Links fan out downward only; there is no edge back up, so a tree can never contain a cycle. Every non-root node has exactly one parent: docs and photos both live inside home, and inside nothing else. A node with no children is a leaf, and photos is one, and so is cv.pdf, one level deeper, because depth has nothing to do with being a leaf. Depth counts edges down from the root: home 0, docs and photos 1, cv.pdf 2. The longest of those chains is the tree's height: height(root) = 2, two edges down to the deepest file.

The code

The lesson's tree as Python objects, with every definition computed rather than asserted. A node holds a value and a list of children:

class Node:
    def __init__(self, val, kids=None):
        self.val, self.kids = val, kids or []

root = Node("home", [Node("docs", [Node("cv.pdf")]), Node("photos")])

def walk(node, depth=0):
    """Every node with its depth (edges from the root), root first."""
    yield node, depth
    for kid in node.kids:
        yield from walk(kid, depth + 1)

def height(node):
    """Edges on the longest path down to a leaf; a leaf's height is 0."""
    return 0 if not node.kids else 1 + max(height(k) for k in node.kids)

nodes = list(walk(root))
print([(n.val, d) for n, d in nodes])     # [('home', 0), ('docs', 1), ('cv.pdf', 2), ('photos', 1)]
print([n.val for n, _ in nodes if not n.kids])            # ['cv.pdf', 'photos']
print(height(root), max(d for _, d in nodes), height(root.kids[0]))   # 2 2 1
print(len(nodes) - 1, sum(len(n.kids) for n, _ in nodes))  # 3 3

The tree's height equals its greatest depth, docs has depth 1 and height 1, and four nodes have three edges. The walk generator is a pre-order traversal; the other orders are in preorder, inorder and postorder traversal.

Trees also arrive as a parent array, where parent[i] is node i's parent: database rows with a parent_id, or an interview input. Checking that such an array really is a tree means one root and no cycles. Each node is walked at most once, so the check is linear:

def is_tree(parent):
    """parent[i] is node i's parent, or None. A tree: one root and no cycles."""
    if sum(p is None for p in parent) != 1:
        return False
    reaches_root = set()
    for start in range(len(parent)):
        path, i = set(), start
        while i is not None and i not in reaches_root:
            if i in path:
                return False                 # walked in a circle
            path.add(i)
            i = parent[i]
        reaches_root |= path                 # each node is walked once: O(n) overall
    return True

print(is_tree([None, 0, 0, 1]), is_tree([None, 2, 1]), is_tree([None, 0, None]))
# True False False

The second array is a cycle between nodes 1 and 2 that never reaches the root; the third has two roots. Finally, everything is checked against brute force on 1,000 seeded arrays, half of them real trees relabelled at random and half arbitrary. is_tree must agree with a breadth-first search from the root that reaches every node, and on real trees the depths from walk must match climbing parent links, height must equal the greatest depth, and the leaves must be exactly the nodes nobody names as a parent:

import random
from collections import deque

def bfs_reaches_all(parent):                 # brute force: one root, and BFS reaches all
    if sum(p is None for p in parent) != 1:
        return False
    kids = {i: [] for i in range(len(parent))}
    for i, p in enumerate(parent):
        if p is not None:
            kids[p].append(i)
    seen, queue = set(), deque([parent.index(None)])
    while queue:
        i = queue.popleft()
        seen.add(i)
        queue.extend(kids[i])
    return len(seen) == len(parent)

def chain(parent, i):                        # depth by climbing parent links
    return 0 if parent[i] is None else 1 + chain(parent, parent[i])

rng = random.Random(35)
ok, valid = True, 0
for _ in range(1000):
    n = rng.randint(1, 12)
    if rng.random() < 0.5:                   # a real tree, relabelled at random
        order = rng.sample(range(n), n)
        parent = [None] * n
        for k in range(1, n):
            parent[order[k]] = order[rng.randrange(k)]
    else:                                    # an arbitrary array: usually not a tree
        parent = [rng.choice([None] + list(range(n))) for _ in range(n)]
    ok &= is_tree(parent) == bfs_reaches_all(parent)
    if is_tree(parent):
        valid += 1
        objs = [Node(i) for i in range(n)]
        for i, p in enumerate(parent):
            if p is not None:
                objs[p].kids.append(objs[i])
        top = objs[parent.index(None)]
        depths = {nd.val: d for nd, d in walk(top)}
        ok &= depths == {i: chain(parent, i) for i in range(n)}
        ok &= height(top) == max(depths.values())
        ok &= sum(1 for nd in objs if not nd.kids) == n - len(set(parent) - {None})
print(ok, valid)                             # True 574

The complexity

• Visiting every node: O(n), and a tree has n - 1 edges, so there is nothing more to visit.
• Depth of one node from a parent array: O(depth), which is O(log n) in a balanced tree and O(n) in a chain.
• Recursive height: O(n) time and O(height) stack, which matters in Python for deep, chain-shaped trees. The Big-O cheat sheet has the costs for the common tree types side by side.

Where it goes wrong

• Swapping depth and height. Depth is measured from the root down to a node; height from a node down to its deepest leaf.
• Edges versus nodes. An off-by-one in every answer if you and the problem disagree on the convention.
• Assuming every input is a tree. Parent arrays from real data can contain cycles or several roots; check before you recurse.
• Unbounded recursion. A degenerate tree of 10,000 nodes is 10,000 nested calls. As of October 2026, CPython's default recursion limit is 1,000, and its standard library has no general-purpose tree type, so an explicit stack or queue is the safe walk.

When it shows up in interviews

Directly as warm-ups, "maximum depth", "count the leaves", "is this a valid tree?", and as the vocabulary under every harder tree question: level-order traversal, diameter, lowest common ancestor and serialisation all assume these words. "Graph valid tree" is the same check as is_tree, starting from an edge list.

How to say it in an interview

"A tree is a set of nodes where one node, the root, has no parent and every other node has exactly one, so there are no cycles and exactly n - 1 edges. A leaf has no children. Depth counts edges from the root down to a node; height counts edges from a node down to its deepest leaf, and the tree's height is the root's height, its greatest depth. I'd confirm whether we count edges or nodes, and for a parent array I'd check for one root and no cycles before treating it as a tree."