1. Introduction

A tree is a hierarchical data structure consisting of nodes connected by edges, with one node designated as the root. Each node can have children nodes, and a node with no children is called a leaf. In a tree, every child has exactly one parent (except the root, which has none).

A binary tree is a special case where each node has at most two children (left and right). A binary search tree (BST) is a binary tree with an ordering property: for each node, all values in its left subtree are smaller, and all values in its right subtree are larger. More generally, an N-ary tree is a rooted tree in which each node can have up to N children.

Tree-based questions are very common in coding interviews. Keywords hinting at tree solutions include “nodes,” “children/parent,” “root/leaf,” “left/right child,” or traversal terms like “preorder,” “inorder,” “postorder,” and “level-order.”

2. Core Idea / Mental Model

A tree can be thought of as a hierarchy where each subtree is a smaller instance of the problem, naturally lending itself to recursive thinking. A good mental model is to consider each node as the root of its own subtree.

Analogies: Family tree, company org chart, file system directory tree.

Common Traversal Patterns:

• Depth-First Search (DFS): Implemented via recursion or an explicit stack.
  • Pre-order: Root -> Left -> Right
  • In-order: Left -> Root -> Right (yields sorted order in a BST)
  • Post-order: Left -> Right -> Root
• Breadth-First Search (BFS): Implemented with a queue, processing nodes level by level (level-order traversal). Useful for shortest path in unweighted trees.

Problem-Solving Strategy:

1. Recursion first: Define the problem in terms of subproblems on children.
2. Identify traversal type: DFS for full exploration/path sums, BFS for levels/shortest path.
3. Top-down vs. Bottom-up: Accumulate results going down (pre-order) or compute from children up (post-order).
4. Consider edge cases: Empty tree, single-node tree, skewed trees.

3. Base Template (Python Tree Traversals)

Below is a Python template for common tree traversals, using a simple TreeNode class.

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

# Pre-order Traversal (Root -> Left -> Right)
def preorder_traversal(root: TreeNode):
    if root is None: return []
    result = [root.val]
    result.extend(preorder_traversal(root.left))
    result.extend(preorder_traversal(root.right))
    return result

# In-order Traversal (Left -> Root -> Right)
def inorder_traversal(root: TreeNode):
    if root is None: return []
    result = []
    result.extend(inorder_traversal(root.left))
    result.append(root.val)
    result.extend(inorder_traversal(root.right))
    return result

# Post-order Traversal (Left -> Right -> Root)
def postorder_traversal(root: TreeNode):
    if root is None: return []
    result = []
    result.extend(postorder_traversal(root.left))
    result.extend(postorder_traversal(root.right))
    result.append(root.val)
    return result

# Level-order Traversal (BFS)
from collections import deque
def level_order_traversal(root: TreeNode):
    if root is None: return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)
    return result

4. Interactive Animation (Pre-order Traversal)

The animation below demonstrates Pre-order Depth-First Search (DFS) on a sample binary tree. Observe how the algorithm visits the current node, then its left subtree, then its right subtree. The "call stack" visually represents the recursion depth.

5. Time & Space Complexity

For an n-node tree:

• Time Complexity (All Traversals): O(n) - each node visited once.
• Space Complexity (DFS - Recursive): O(h) for call stack, where h is tree height. Worst case O(n) for skewed tree, best/average O(log n) for balanced tree.
• Space Complexity (DFS - Iterative with Stack): O(h), similar to recursive.
• Space Complexity (BFS - Level-order): O(w) where w is max width of tree. Worst case O(n) for a complete tree.

(Output list space is O(n) if storing all node values.)

6. Common Pitfalls

• Incorrect or Missing Base Case: Not handling None nodes in recursion.
• Off-by-One Errors: In height/depth calculations.
• Infinite Recursion / Cycles: Usually not an issue for standard trees but be careful if modifying structure or treating as general graph.
• Null Child Handling: Accessing properties of None children (e.g., node.left.val without checking node.left).
• Using Wrong Traversal Approach: E.g., using DFS for shortest path when BFS is better.
• Mistaking Binary Tree vs BST: Assuming BST properties for a general binary tree.
• BST Edge Cases: Incorrect min/max bounds for validation, mishandling duplicates.
• Not Accounting for Recursion Return Values: Forgetting to use or propagate results from recursive calls.
• Edge Cases & Skewed Trees: Test with empty, single-node, and skewed trees.

7. Frequently Asked Tree Problems (LeetCode)

The following are some of the most frequently asked LeetCode problems involving trees:

Solving these problems will solidify your understanding of tree fundamentals.