Tree

The tree data structure is one of the most important concepts to master when preparing for coding interviews. Trees appear frequently in LeetCode problems because they are an intuitive way to represent hierarchical relationships and because they naturally support recursive problem-solving. Once you understand how trees work and how to traverse them correctly, a large class of interview problems becomes far more manageable.

In simple terms, a tree organizes data in a hierarchy, starting from a single top node and branching outward. Many real-world systems follow this pattern, which is why interviewers rely so heavily on tree-based questions to evaluate problem-solving ability.

What is a tree?

A tree is a non-linear data structure made up of nodes connected by edges. Unlike arrays or linked lists, trees do not store data sequentially. Instead, they branch out, allowing one node to connect to multiple others in a parent–child relationship.

A structure qualifies as a tree when the following conditions are met:

• There is exactly one root node, which acts as the starting point.
• Every node except the root has exactly one parent.
• Each node can have zero or more children.
• There are no cycles, meaning you cannot loop back to a node once you move away from it.
• All nodes are connected, either directly or indirectly, to the root.

Real-world intuition

Trees are easier to understand when you map them to familiar systems:

• A file system, where folders contain subfolders and files.
• A company hierarchy, where managers supervise employees.
• A website structure, where pages branch into categories and subcategories.

Each example starts from a single entry point and expands downward, just like a tree in DSA.

Tree terminology for coding interviews

Coding interview problems often rely heavily on precise terminology, so understanding the following terms is helpful:

• Node: A single element in the tree. It’s the basic unit containing data and pointers to children.
• Edge: The connection between a parent and a child
• Root: The top-most node of the tree (no-parent).
• Leaf: A node with no children.
• Subtree: A node along with all of its descendants.
• Depth: The number of edges from the root to a specific node.
• Height: The number of edges on the longest path from a node to a leaf.

Depth vs. height of a tree

Two commonly confused terms are depth and height of a tree. Depth and height both measure distance in a tree, but they’re measured in opposite directions.

• Depth of a node is the number of edges from the root to that node.
  • The root has depth 0, and depth increases by 1 as you move down each level.
• Height of a node is the number of edges on the longest path from that node down to a leaf.
  • A leaf has height 0, and height is computed from children upward.

A simple way to remember it is that depth is measured from the root downward, while height is measured from the leaves upward.

Structure of a tree node

Each node in a tree consists of three specific components:

• Node value: This is the actual information/data (integer, string, etc.) that the node is meant to hold.
• Reference to the left child: This is a pointer (or reference) to another tree node that acts as the left child. If there is no left child, this is set to NULL.
• Reference to the right child: This is a pointer (or reference) to the right child. If there is no right child, it is set to NULL.

Let’s look at the code definition for a tree node in Python:

# Definition for a Tree Node

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

Types of trees

Not all trees behave the same way. In practice, interview problems usually revolve around three common variations, general (N-ary) trees, binary trees, and binary search trees (BSTs), each with its own structure and properties.

General (N-ary) trees

In a general tree, each node can have any number of children. These trees are commonly used to model real-world hierarchies, such as folder structures or category systems.

Binary trees

A binary tree restricts each node to at most two children: a left child, and a right child. Most LeetCode tree problems use binary trees because they are simple to represent and rich enough to express complex logic.

Binary search trees (BSTs)

A binary search tree is a binary tree with an ordering constraint:

• All values in the left subtree are smaller than the node’s value.
• All values in the right subtree are larger than the node’s value.

This property allows efficient searching, insertion, and deletion when the tree is balanced. However, if a BST becomes skewed, its performance degrades and can resemble that of a linked list.

Common binary tree forms

Some problems describe binary trees using structural properties:

• Full binary tree: Every node has either zero or two children.

• Complete binary tree: Levels of tree are filled from left to right, and only the last level may be partially filled.

• Perfect binary tree: All internal nodes have two children and all leaves are at the same depth.

• Balanced binary tree: The left and right subtree heights at each node differ by at most 1).

• Skewed binary tree: Most nodes have only one child, so the tree behaves like a linked list.

These distinctions appear frequently in heap-related and counting problems, while balanced vs skewed shapes are especially important for understanding time complexity and recursion depth.

Tree traversal techniques

Tree traversal refers to the order in which nodes are visited. Almost every tree problem relies on choosing the correct traversal strategy.

Depth-first search (DFS)

Depth-first search (DFS) visits nodes by going as deep as possible along one branch before returning to explore the next, which is why it maps naturally to recursive tree solutions. In binary trees, DFS is most commonly written in three standard orders: preorder, inorder, and postorder.

Preorder traversal (Root → Left → Right)

The traversal starts by visiting the root, followed by the left subtree and then the right subtree. Preorder traversal is useful when a node needs to be processed before its children, such as when constructing paths or copying or serializing a tree.

Code for preorder traversal (recursive)

Preorder traversal processes the root before its subtrees, making it a natural choice when a node must be handled before its children. Let’s look at its implementation in Python.

def preorderRecursive(root):
    res = []

    def dfs(node):
        # 1) Stop at null nodes
        if not node:
            return

        # 2) Visit root first
        res.append(node.val)

        # 3) Traverse left subtree
        dfs(node.left)

        # 4) Traverse right subtree
        dfs(node.right)

    dfs(root)
    return res

Time complexity: O(N), as each node is visited once.

Space complexity: O(H), where H is the height of the tree due to the recursion stack (worst case O(N) for a skewed tree).

Inorder traversal (Left → Root → Right)

The traversal visits the left subtree first, then the root, and finally the right subtree. Inorder traversal is especially important for binary search trees because it visits node values in sorted order.

Code for inorder traversal

Inorder traversal visits the left subtree first, then the root, and finally the right subtree, which is especially useful for binary search trees. Let’s look at its implementation in Python.

def inorderRecursive(root):
    res = []

    def dfs(node):
        # 1) Stop at null nodes
        if not node:
            return

        # 2) Traverse left subtree
        dfs(node.left)

        # 3) Visit root
        res.append(node.val)

        # 4) Traverse right subtree
        dfs(node.right)

    dfs(root)
    return res

Time complexity: O(N)

Space complexity: O(H) recursion stack (worst case O(N) if skewed).

Postorder traversal (Left → Right → Root)

The traversal visits both subtrees before the root. Postorder traversal is ideal when a node’s computation depends on results from its children, which is common in height calculations, balance checks, and tree dynamic programming problems.

Code for postorder traversal

Postorder traversal processes both subtrees before the root, which makes it well-suited for problems where a node depends on results computed from its children. Let’s look at its implementation in Python.

def postorderRecursive(root):
    res = []

    def dfs(node):
        # 1) Stop at null nodes
        if not node:
            return

        # 2) Traverse left subtree
        dfs(node.left)

        # 3) Traverse right subtree
        dfs(node.right)

        # 4) Visit root last
        res.append(node.val)

    dfs(root)
    return res

Time complexity: O(N)

Space complexity: O(H) recursion stack (worst case O(N) if skewed).

Breadth-first search (BFS): Level-order traversal

Breadth-first search (BFS) visits a tree level by level from top to bottom, typically using a queue to process nodes in the order they are discovered. Because BFS groups nodes by their depth, it is a natural fit for problems that involve:

• Level-based output, such as level-order traversal or averages per level
• Depth-related questions, such as minimum depth or maximum depth
• Shortest paths in tree-like structures, where each edge has equal cost
• Tree “views”, such as the right side view or left side view
• Alternating level patterns, such as zigzag or spiral traversal

Code for level-order traversal

Level-order traversal visits nodes breadth-first, processing the tree one level at a time using a queue. Let’s look at its implementation in Python.

from collections import deque

def levelOrder(root):
    # 1) Handle empty tree
    if not root:
        return []

    res = []
    q = deque([root])  # 2) Queue stores nodes to process level-by-level

    while q:
        level = []
        level_size = len(q)  # 3) Current queue size = number of nodes in this level

        # 4) Process exactly one full level
        for _ in range(level_size):
            node = q.popleft()
            level.append(node.val)  # Visit node

            # 5) Add children for the next level
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)

        # 6) Store this level’s values
        res.append(level)

    return res

Time complexity: O(N)

Space complexity: O(W) queue, where W is the maximum width of the tree (worst case O(N)).

Trees reward structured thinking. Once you learn how to classify problems by traversal type and recognize common patterns, tree questions become less intimidating and far more predictable. Mastering trees is not about memorizing solutions, but about understanding how information flows through a hierarchy.