Skip to content
Hello Python
Data Structure1 Practice2 Interview

Tree

Hierarchical acyclic structure used for recursive aggregation, search, and ordered relationships. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Tree when the prompt's constraints and required operations match this shape: Hierarchical acyclic structure used for recursive aggregation, search, and ordered relationships.

Pybit studies a professional Tree interview workspace with precise technical objects.
On this page · Mental Model

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Tree Code Labs

Mental Model

A rooted tree is a hierarchy with one root, one parent for every other node, and a unique path from the root to each node. Removing any parent-child edge separates one subtree. This makes subtree results independent and composable, even when nodes have more than two children.

Rooted Hierarchy and Subproblems

Define a recursive helper over one node’s complete subtree. Preorder performs node work before its children; postorder waits until every child result is ready. A tree needs no visited set when input already provides directed child lists and guarantees acyclicity.

The Python recursion model(opens in a new tab) still limits safe call depth, so an explicit stack is appropriate for a long chain.

Compare Traversal Orders

Traversal order is part of the algorithm, not presentation. Preorder is useful for propagation and serialization; postorder supports aggregation and deletion; breadth order groups equal depth. For ordered children, preserve their stated order when pushing onto a LIFO stack.

Compare Tree Traversal Orders

Reference
def traversal_orders(children, root):
    preorder = []
    postorder = []
    def visit(node):
        preorder.append(node)
        for child in children[node]:
            visit(child)
        postorder.append(node)
    visit(root)
    return preorder, postorder
Practice

Implement traversal_orders(children, root). Return preorder and postorder lists while preserving each node's authored child order.

Public tests

  • Verify traversal timing

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Derive Parent and Depth State

An undirected acyclic edge list becomes a rooted tree after choosing a root. Traverse once, skip the parent edge, and assign each child’s parent and depth. The parent check replaces a general visited set because a tree has no alternate route back to an earlier node.

Root an Undirected Tree

Reference
def parent_and_depth(node_count, edges, root):
    adjacency = [[] for _ in range(node_count)]
    for left, right in edges:
        adjacency[left].append(right)
        adjacency[right].append(left)
    parent = [-2] * node_count
    depth = [-1] * node_count
    parent[root] = -1
    depth[root] = 0
    stack = [root]
    while stack:
        node = stack.pop()
        for neighbor in adjacency[node]:
            if neighbor == parent[node]:
                continue
            parent[neighbor] = node
            depth[neighbor] = depth[node] + 1
            stack.append(neighbor)
    return parent, depth
Practice

Implement parent_and_depth(node_count, edges, root). Return parent and depth arrays after rooting the undirected tree; the root parent is -1.

Public tests

  • Verify parent and depth propagation

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose a Tree Representation

Use node objects when recursive structure is supplied directly, child lists for arbitrary branching, an adjacency list for undirected edges, and parent arrays for ancestor/depth preprocessing. A binary tree specializes child count; a BST adds ordering. A graph is required when cycles or multiple paths are allowed.

Common Pitfalls

  • Treating an undirected parent edge as a child causes immediate backtracking forever.
  • Using preorder when the answer depends on completed child results reads unfinished state.
  • Assuming every tree is binary drops later children.
  • Copying a full path at each node can create quadratic work on a chain.
  • Recursive code can exceed Python’s recursion limit even though the algorithm is O(n).

Explain It in an Interview

State the root, representation, and return contract for one subtree. Name why the chosen traversal order matches when information becomes available. Give O(n) time because each node/edge is processed once and O(h) recursive space or O(w) breadth frontier space.

Profile a Binary Tree(opens in a new tab) is one binary specialization. Binary Tree Level Order(opens in a new tab) tests whether breadth grouping is chosen instead of generic recursion.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Core Tree workflowO(n)O(n)Breadth-first traverse reachable complete-tree indexes while tracking each node level and whether it has present children.

Space

O(n) for the demonstrated Tree workflow.

Assumptions

  • State the concrete operation and representation before claiming a bound; tree height and graph density can change it.
  • The bound counts the operations in Profile a Binary Tree and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

  1. State the precise Tree invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Traverse only nodes reachable from the root. This remains true after every accepted operation.
  3. Distinguish total nodes, root-to-leaf height, and leaf count. This remains true after every accepted operation.

When To Use Or Avoid Tree

Use It When

  • Use Tree when its representation directly supports the prompt's repeated query or update.
  • Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

  • Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
  • Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Tree invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def binary_tree_profile(level_order):
    pass

Use instead

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]

Where you will hit this: Profile a Binary Tree(opens in a new tab)

Breaking the central invariant

Counts every non-None array entry, including values that are unreachable below a missing parent.

Prevent it: Keep this invariant visible while editing: State the precise Tree invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def binary_tree_profile(level_order):
    values = [value for value in level_order if value is not None]
    return [len(values), len(values), 1 if values else 0]

Use instead

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]

Where you will hit this: Profile a Binary Tree(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(n).

Avoid

def binary_tree_profile(level_order):
    values = [value for value in level_order if value is not None]
    return [len(values), len(values), 1 if values else 0]

Use instead

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]

Where you will hit this: Binary Tree Level Order(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.