Hamropedia

DSA · Topic 7 of 18 · Trees & Graphs

Trees

Trust the recursion: solve it for the left and right children, then combine at the node.

By Manoj Kumar Thapa

AI Software Engineer ·

15 problems · O(n): every node visited once time, O(h) for recursion (h = height); O(width) for BFS space

Step 1 Understand it

Remember it by

Trust the recursion: solve it for the left and right children, then combine at the node.

Watch it happen

AnimationTrees: let each node ask its children, or visit level by level
Read the animation as text
  1. How deep is the tree? Ask each node: "how deep is the tree below you?" A node waits for both children to answer, then returns 1 + the bigger answer. An empty child returns 0.
  2. 9 is a leaf: both children are empty (0). It returns 1 + max(0, 0) = 1.
  3. 15 is a leaf: both children are empty (0). It returns 1 + max(0, 0) = 1.
  4. 7 is a leaf: both children are empty (0). It returns 1 + max(0, 0) = 1.
  5. 20 has heard from both children: left 1, right 1. It returns 1 + max(1, 1) = 2.
  6. 3 has heard from both children: left 1, right 2. It returns 1 + max(1, 2) = 3.
  7. The root returns 3: the answer. Children answer before parents (post-order), and each node is visited once: O(n).

The idea

Most tree problems are depth-first: a function that handles one node by calling itself on the left and right children and combining their answers. Problems about 'levels' or 'the closest' use breadth-first search with a queue instead.

Picture it

flowchart TD
  A(("3")) --> B(("9"))
  A --> C(("20"))
  C --> D(("15"))
  C --> E(("7"))
  B -.->|"returns 1"| A
  C -.->|"returns 2"| A
Answers flow upwards: each node combines what its children return (here, the depth).

Analogy

A manager asking two team leads for their team's number, adding their own, and passing the total up. Nobody needs to see the whole company.

Where the analogy breaks

Real managers can be asked twice. In recursion, the base case (an empty child returns 0, None or True) is what stops it — forget it and you crash.

More detail

What it is

A Tree is just like a Linked List, but instead of one 'next' pointer, a node can have multiple pointers (like 'left' and 'right'). It branches out exactly like a real tree! The most common type is a Binary Tree, where each node has at most two children. The very top node is called the 'root', and nodes with no children are called 'leaves'. Trees are incredible for representing hierarchical data, like file systems, company org charts, or family trees.

When to use it

  • When data is naturally hierarchical.
  • When you need to perform fast O(log N) searches, insertions, and deletions (using a Binary Search Tree).
  • When you need to traverse data in a specific order (In-order, Pre-order, Post-order).

How it works

Because trees are recursive by nature (every child is the 'root' of its own smaller subtree), the most elegant way to work with them is using Recursion! You write a function that does something to the current node, and then simply calls itself on the left child and the right child. You'll almost always use Depth-First Search (DFS) with recursion, or Breadth-First Search (BFS) using a Queue to go level-by-level.

Example walkthrough

Input: root = [4,2,7,1,3], invert it

  1. At root 4: swap left (2) and right (7). Recursively call invert(2) and invert(7).
  2. At 2: swap 1 and 3.
  3. At 7: swap null and null.
  4. All subtrees inverted. The whole tree is now a mirror image!

Result: [4,7,2,null,null,3,1]

Related patterns

  • Depth-First Search (DFS): The standard recursive way to go deep into a tree before coming back up.

Step 2 Recognise it

Words that signal it

  • The input is a binary tree (TreeNode)
  • 'Depth', 'height', 'diameter', 'balanced', 'path sum' → DFS
  • 'Level by level', 'right side view', 'minimum depth' → BFS
  • 'Binary search tree': left < node < right

Don't confuse it with

  • Graphs: A tree has no cycles and one parent per node, so no visited set is needed. If a node can be reached two ways, it's a graph.
  • Backtracking: Listing every root-to-leaf path is backtracking on a tree; computing one value from the children is plain DFS.

Gut check

Can I answer for a node if I knew the answer for its children? → recursive DFS. Levels? → BFS.

How to recognise it in an interview

The input is a TreeNode. The problem asks about 'depth', 'lowest common ancestor', or 'level order'.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

python
def dfs(node):
    if not node:                      # base case
        return 0
    left = dfs(node.left)             # trust it: the answer for the left subtree
    right = dfs(node.right)           # and for the right subtree
    return 1 + max(left, right)       # combine at this node
The same template in Java
text
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        // Swap the children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        // Recursively do the same for the rest of the tree
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

BFS level by level

python
from collections import deque

def levels(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):           # exactly one level
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out
TimeO(n): every node visited once
SpaceO(h) for recursion (h = height); O(width) for BFS

Common mistakes

  • Missing the base case if not node: return ….
  • Checking BST validity only against the direct parent instead of passing down min and max bounds.
  • Mixing what a function returns with the global answer (Diameter: return the height, update the diameter separately).
  • Not trusting the recursion! Beginners often try to manually track tree depth with complicated loops instead of just letting the call stack do the work.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

Easy example: Maximum Depth of Binary Tree

Input: root = [3, 9, 20, null, null, 15, 7]

nodeleft depthright depthreturns
9001 + max(0, 0) = 1
15001 + max(0, 0) = 1
7001 + max(0, 0) = 1
20111 + max(1, 1) = 2
3121 + max(1, 2) = 3

Result: 3

Notice: The order of the rows is the order the calls finish: children always finish before their parent (post-order).

python
def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Medium example: Binary Tree Level Order Traversal (BFS)

Input: root = [3, 9, 20, null, null, 15, 7]

queue at startlevel sizethis levelqueue after
[3]1[3][9, 20]
[9, 20]2[9, 20][15, 7]
[15, 7]2[15, 7]empty

Result: [[3], [9, 20], [15, 7]]

Notice: Freezing len(q) at the start of each round is what separates one level from the next.

python
from collections import deque

def level_order(root):
    out, q = [], deque([root] if root else [])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        out.append(level)
    return out

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

  1. Invert Binary Tree Easy

    Mirror a binary tree (swap every left and right child).

    Show answer

    Technique: DFS recursion

    The clue: Do the same simple thing at every node.

    The trick: Swap the children, then invert both subtrees.

  2. Maximum Depth of Binary Tree Easy

    Return the number of nodes on the longest root-to-leaf path.

    Show answer

    Technique: DFS returning height

    The clue: 'Depth' = combine the children's answers.

    The trick: Depth = 1 + max(left depth, right depth); an empty tree is 0.

  3. Diameter of Binary Tree Easy

    Find the longest path (in edges) between any two nodes.

    Show answer

    Technique: DFS returning height, global best

    The clue: The longest path bends at some node: left height + right height.

    The trick: Return the height from each call, and update a global best with left + right at every node.

  4. Balanced Binary Tree Easy

    Decide whether every node's two subtree heights differ by at most 1.

    Show answer

    Technique: DFS returning height (or −1 for unbalanced)

    The clue: A height check at every node.

    The trick: Return the height if balanced, or −1 to signal 'unbalanced' all the way up, so it's O(n).

  5. Same Tree Easy

    Decide whether two binary trees are identical.

    Show answer

    Technique: DFS on both trees together

    The clue: Compare structure and values node by node.

    The trick: Both empty → true; one empty or values differ → false; else recurse on left and right pairs.

  6. Subtree of Another Tree Easy

    Decide whether one tree appears exactly as a subtree of another.

    Show answer

    Technique: DFS + Same Tree check

    The clue: 'Appears somewhere inside' = try every node as a starting point.

    The trick: At every node of the big tree, run Same Tree with the small one.

Medium

  1. Lowest Common Ancestor of a Binary Search Tree Medium

    In a binary search tree, find the lowest node that has both p and q below it (or is one of them).

    Show answer

    Technique: BST property walk

    The clue: It's a binary search tree: values tell you which way to go.

    The trick: If both values are smaller, go left; both bigger, go right; otherwise you've found the split point.

  2. Binary Tree Level Order Traversal Medium

    Return the node values level by level.

    Show answer

    Technique: BFS with a queue

    The clue: 'Level by level'.

    The trick: Process exactly len(queue) nodes per round; that's one level.

  3. Binary Tree Right Side View Medium

    Return the values you'd see looking at the tree from the right.

    Show answer

    Technique: BFS, last node of each level

    The clue: 'What you see from the side' = one node per level.

    The trick: Do a level-order traversal and keep the last value of each level.

  4. Count Good Nodes In Binary Tree Medium

    Count nodes that are at least as large as every node on the path from the root to them.

    Show answer

    Technique: DFS passing the path maximum down

    The clue: A condition about the path from the root.

    The trick: Pass the largest value seen so far into each call; a node is good if it's ≥ that value.

  5. Validate Binary Search Tree Medium

    Decide whether a binary tree is a valid binary search tree.

    Show answer

    Technique: DFS with min and max bounds

    The clue: Every node must fit the rules of all its ancestors, not just its parent.

    The trick: Pass an allowed range (low, high) down; going left lowers high, going right raises low.

  6. Kth Smallest Element In a BST Medium

    Return the k-th smallest value in a binary search tree.

    Show answer

    Technique: In-order traversal

    The clue: In a BST, in-order visits values in sorted order.

    The trick: Do an in-order traversal (iteratively with a stack) and stop at the k-th value.

  7. Construct Binary Tree From Preorder And Inorder Traversal Medium

    Rebuild a binary tree from its preorder and inorder lists.

    Show answer

    Technique: Recursion with an index map

    The clue: Preorder gives roots; inorder splits left from right.

    The trick: The first preorder value is the root; its position in inorder tells you the size of the left subtree. Use a value → index map.

Hard

  1. Binary Tree Maximum Path Sum Hard

    Find the largest sum of any path between two nodes.

    Show answer

    Technique: DFS returning the best one-sided path, global best

    The clue: A path bends at most once, like the diameter.

    The trick: Each call returns node + max(0, best child path); update the global best with node + left gain + right gain.

  2. Serialize And Deserialize Binary Tree Hard

    Turn a binary tree into a string and rebuild it exactly.

    Show answer

    Technique: Preorder DFS with null markers

    The clue: You need the shape, not just the values.

    The trick: Write values in preorder with 'N' for empty children; read them back with the same recursion.

What to say in the interview

'Because trees are inherently recursive structures, I will use Depth-First Search to elegantly traverse the nodes in O(N) time.'

Follow-up prep

Do you know the difference between Pre-Order, In-Order, and Post-Order traversals?