Trees

A tree is a hierarchical data structure consisting of nodes connected by edges. Unlike linear structures (arrays, linked lists), trees represent hierarchical relationships.

The Family Tree Analogy: Think of a family tree:

• •The oldest ancestor is the root
• •Each person (node) can have children
• •Nodes with no children are leaves
• •Every node has exactly one parent (except root)

Visual Representation:

Why Trees Matter:

• •File systems (folders contain files/folders)
• •HTML/DOM (elements contain elements)
• •Organization charts
• •Decision trees
• •Expression parsing
• •Database indexes (B-trees)

Binary Trees: Each node has at most 2 children (left and right). Most interview questions focus on binary trees.

Before solving any tree problem, understand the node structure.

The Building Block:

Visual Representation:

Building a Tree Manually:

Key Insight: Unlike linked lists (one pointer), tree nodes have TWO pointers. This creates branching, which is why we need different traversal strategies.

Master these terms - interviewers use them freely.

Node Relationships:

Measurements:

• •Depth of node: Distance from root (root depth = 0)
• •Height of node: Distance to deepest leaf below it
• •Height of tree: Height of root = max depth of any leaf
• •Level: All nodes at same depth

Example:

Types of Binary Trees:

Tree problems test multiple skills simultaneously.

What Interviewers Are Really Testing:

1. •Recursion Skills - Can you think recursively?
2. •Edge Case Handling - Null nodes, single node, skewed trees
3. •Choosing Right Traversal - Pre/In/Post/Level order
4. •State Management - Passing info down vs returning info up

Frequency in Interviews:

• •FAANG: 20-25% of coding rounds include tree problems
• •Most common: Max Depth, Validate BST, LCA, Level Order
• •Hardest: Serialize/Deserialize, Binary Tree Maximum Path Sum

The Two Fundamental Approaches:

Golden Rule: Most tree problems reduce to "when do I process the node relative to its children?" Answer that, and you've chosen your traversal.

The key decision in tree problems: depth-first or breadth-first?

DFS (Depth-First Search):

Use DFS when:

• •Computing values that bubble UP (height, subtree sums)
• •Path problems (root to leaf)
• •Tree structure problems (validate BST, same tree)
• •Most tree problems!

BFS (Breadth-First Search):

Use BFS when:

• •Level-order operations (level averages, zigzag)
• •Finding nodes at specific depth
• •Right/left side view
• •Shortest path in unweighted trees

Quick Decision:

DFS has three orderings based on WHEN you process the current node.

The Key Question: When do I "visit" (process) the node?

Preorder (Node → Left → Right):

Inorder (Left → Node → Right):

Postorder (Left → Right → Node):

Memory Trick:

• •Pre = process pre-children (before)
• •In = process in-between children
• •Post = process post-children (after)

Preorder processes the node BEFORE its children. Think "top-down."

Visual Trace:

When to Use Preorder:

• •Serialization: Process node before children so you know structure
• •Copying a tree: Create node, then recursively copy children
• •Path from root: Build path as you go down
• •Printing tree structure: Parent printed before children

Inorder processes the node BETWEEN its children. For BST, this gives SORTED order!

Visual Trace:

Why BST + Inorder = Sorted: In BST: left < node < right Inorder visits: left, then node, then right → Visits nodes in ascending order!

When to Use Inorder:

• •Kth smallest in BST: Stop at kth node
• •Validate BST: Check if output is sorted
• •Convert BST to sorted array/list

Postorder processes the node AFTER its children. Think "bottom-up."

Visual Trace:

Why Postorder for "Bottom-Up": You need children's results BEFORE you can compute parent's result.

Example - Height Calculation:

When to Use Postorder:

• •Height/Depth: Need children's heights first
• •Diameter: Need both subtree heights
• •Delete tree: Delete children before parent
• •Subtree sums: Sum children before adding to parent

Convert recursion to iteration using an explicit stack. Useful for deep trees to avoid stack overflow.

Key Insight: The call stack in recursion can be replaced with our own stack.

Iterative Preorder (Easiest):

Iterative Inorder: Trickier - need to go left first, then process, then go right.

Iterative Postorder: Trickiest - need to process AFTER both children. Use reverse trick or two stacks.

BFS processes nodes level by level using a queue.

The Algorithm:

1. •Start with root in queue
2. •For each level:
   • Save queue size (nodes in this level)
   • Process exactly that many nodes
   • Add their children for next level

Visual Trace:

Why Save Size? The queue contains nodes from multiple levels. By saving size at loop start, we know exactly how many belong to current level.

A classic postorder problem: you need children's depths before computing parent's depth.

The Key Insight:

You MUST know children's depths first → Postorder!

Visual Trace:

Alternative: BFS Count number of levels. Each level = 1 depth.

The diameter is the longest path between ANY two nodes. Critical insight: the path may NOT pass through root!

The Key Insight: For each node, the longest path THROUGH that node = leftHeight + rightHeight.

We need to check this for EVERY node and track the maximum.

Example:

The Pattern: Postorder + Global Variable Compute heights (postorder), but track maximum path at each node using a closure/class variable.

A Binary Search Tree (BST) maintains a special ordering property.

The BST Property: For every node:

• •ALL nodes in left subtree < node
• •ALL nodes in right subtree > node

Valid BST:

Invalid BST:

BST Operations:

Key BST Insight: Inorder traversal gives SORTED order!

Checking if a tree is a valid BST is trickier than it looks.

Common Mistake - Only Check Children:

This misses cases where a node violates an ancestor's constraint!

Correct Approach - Pass Bounds Down: Each node must be within a valid range:

• •Left child: (min, parent)
• •Right child: (parent, max)

Visual:

Find the deepest node that is an ancestor of both nodes p and q.

Visual:

Algorithm for Binary Tree: Postorder search - look for p and q in both subtrees:

1. •If current is null, p, or q → return current
2. •Search left subtree
3. •Search right subtree
4. •If both sides found something → current is LCA
5. •Otherwise return whichever side found something

Algorithm for BST (Faster): Use BST property:

• •If both p and q < node → LCA is in left subtree
• •If both p and q > node → LCA is in right subtree
• •Otherwise → current node is LCA (split point)

Path problems come in several varieties. Know the differences!

Type 1: Root-to-Leaf Path Sum "Does any root-to-leaf path sum to target?"

Type 2: Any Path (Can Start/End Anywhere) "Find max sum of any path" - much harder! Path can start and end at any node.

Type 3: Count Paths with Sum "How many paths sum to target?" (Path Sum III) Paths can start anywhere but must go downward.

Convert a tree to a string and back. A hard problem that tests deep understanding.

The Challenge: A tree structure must be fully recoverable from the string.

Approach: Preorder + Null Markers

Why Preorder Works: Preorder visits root first, so we know the structure from top-down. Combined with null markers, we know exactly when a subtree ends.

Rebuild a tree given two traversal arrays. Classic interview problem!

What You Need:

• •Preorder + Inorder → Unique tree
• •Postorder + Inorder → Unique tree
• •Preorder + Postorder → NOT unique (unless full binary tree)

Why Inorder is Special: Inorder tells you which nodes are in left vs right subtree.

Algorithm (Preorder + Inorder):

Return values visible from the right side - a BFS classic!

Visual:

Approach 1: BFS Process level by level, take last node of each level.

Approach 2: DFS Modified preorder: Root → Right → Left Track depth, add node if visiting new depth for first time.

Master these edge cases to avoid interview pitfalls.

1. Empty Tree (root = null)

2. Single Node

3. Skewed Tree (Like a Linked List)

4. Complete vs Incomplete

5. Null Children

6. Integer Overflow in BST Validation

7. Duplicate Values Some BST problems allow duplicates. Clarify with interviewer!

Quick reference for choosing the right approach:

Decision Tree:

Copy-paste ready templates for common tree operations.

Template 1: DFS Recursive

Template 2: BFS Level Order

Template 3: BST Validation

Template 4: LCA

Template 5: Postorder with Global Max