Skip to content
Tutorials Center
My learning

Topics

Lesson 95 of 225 ยท Trees

Common Tree Problems

Solve classic binary tree problems in Python, brute force first: diameter, lowest common ancestor, path sum, same and symmetric tree, invert, serialize, subtree.

Tree questions look different on the surface, but nearly all of them are solved by one of two recipes you already know: a recursive function that combines the answers of the left and right subtrees, or a level-order walk with a queue. This lesson works through eight of the most common problems. For each one we begin with the straightforward approach, point out what it wastes, and then improve it, always stating the cost.

Every example builds on this node class and the level-order build_tree helper from binary trees. Each TryIt repeats them so that it runs on its own.

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

A thinking checklist for any tree problem: What is the answer for an empty tree? What do I need to know from each child? What do I do with those two answers at the current node? Is some information passed down (a running sum, a range) or up (a height, a count)?

Problem 1: Diameter of a binary tree

The diameter is the number of edges on the longest path between any two nodes. The path does not have to pass through the root.

TEXT
        1
       / \
      2   3        longest path: 4 - 2 - 1 - 3 (3 edges) or 4 - 2 - 5 (2)
     / \          here the diameter is 3
    4   5

Brute force. For every node, compute the height of its left and right subtrees (a full recursion each time) and take left_height + right_height + 2 as the longest path through that node. The answer is the maximum over all nodes. The heights are recomputed again and again: O(n^2) on a skewed tree, O(n log n) on a balanced one.

Better. Compute the height bottom-up and, at each node, update a running best with the path through that node. One pass, O(n) time, O(h) space. The function returns the height (information passed up) while quietly recording the answer on the side.

Python Diameter: brute force vs one pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second tree's longest path (7 - 5 - 3 - 2 - 4 - 6 - 8, 6 edges) bends at node 2, below the root. That is why we must check every node, not only the root.

Problem 2: Lowest common ancestor (LCA)

The lowest common ancestor of two nodes p and q is the deepest node that has both of them in its subtree (a node counts as its own descendant).

Brute force. Find the root-to-p path and the root-to-q path (two DFS passes, O(n) time and space each), then walk both paths together until they diverge. The last shared node is the LCA.

Better. One recursion. For each node, ask both subtrees "do you contain p or q?" If p and q are found in different subtrees, this node is the split point. If only one side reports something, pass that result up.

TEXT
lca(node, p, q):
    if node is None or node is p or node is q:  return node
    left  = lca(node.left,  p, q)
    right = lca(node.right, p, q)
    if left and right:  return node     # p and q are on different sides
    return left or right

In a binary search tree it gets simpler still: if both keys are smaller than the node, go left; if both are larger, go right; otherwise the current node is the LCA. That is O(h) time and O(1) extra space.

Python Lowest common ancestor in two ways

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All three agree. The (2, 4) case shows the "node is its own ancestor" rule: 4 lies below 2, so the answer is 2.

Problem 3: Path sum

Does any root-to-leaf path add up to a target? Pass the remaining target down: at each node subtract its value, and at a leaf check whether the remainder is zero. A node with one child is not a leaf, so keep descending.

Harder version: how many downward paths (starting and ending anywhere) add up to a target?

Brute force. Treat every node as a possible starting point and run a DFS that counts paths from it. O(n^2) on a skewed tree, O(n log n) on a balanced one.

Better. Use prefix sums, the idea from prefix sums applied to root-to-node paths. Keep a dictionary of how many times each running sum has occurred on the current path. If the running sum now is s, then each earlier prefix equal to s - target marks a path that ends here and sums to target. Undo the count when you leave a node. O(n) time, O(h) space.

Python Path sum and counting paths with prefix sums

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Root-to-leaf sums here are 21, 16, 18 and 18, so a target of 22 gives False and 21 gives True. The downward paths that sum to 8 are 5-3, 5-2-1 and -3-11, so both counting versions print 3.

Problem 4: Same tree and symmetric tree

Are two trees identical? Same shape and same values. Compare roots, then recurse on both pairs of children.

Is a tree a mirror of itself? Same idea, but compare the left of one with the right of the other. This pair-of-nodes recursion is worth remembering.

Python Same tree and symmetric tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both run in O(n) time (stopping at the first difference) and O(h) space. The lopsided tree has equal values on both sides but the wrong layout: a mirror image would need the 3 on the left of one side and on the right of the other.

Problem 5: Invert a binary tree

Swap the left and right child of every node. The recursion is almost too short: invert the two subtrees, then swap them (the order of the swap and the recursive calls does not matter, as long as every node is swapped once).

Python Invert a binary tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

O(n) time; O(h) space recursively, O(w) with the queue.

Problem 6: Serialize and deserialize

To store a tree in a file or send it over a network, you need a string form from which the exact tree can be rebuilt. A single traversal is not enough, but a preorder traversal that writes a marker for every missing child is: the markers remove all ambiguity.

TEXT
      1
     / \          serialized (preorder with # for empty):
    2   3         1,2,#,#,3,4,#,#,5,#,#
       / \
      4   5

Deserializing reads the tokens in the same order: take a token; if it is #, return None; otherwise create a node and build its left subtree, then its right subtree from the following tokens.

Python Serialize and deserialize a tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both directions are O(n). The string is about twice as long as the number of nodes because of the # markers. The iter object works like a shared cursor, so every recursive call continues exactly where the previous one stopped.

Problem 7: Is one tree a subtree of another?

Given root and sub, does root contain a node whose subtree is identical to sub?

Brute force. At every node of root, call is_same(node, sub). If root has n nodes and sub has m, that is O(nยทm) in the worst case.

Better. Serialize both trees (with markers, and with a delimiter in front of each value so that 12 is not confused with 2), then search for the string of sub inside the string of root. With a linear-time substring search such as KMP this is O(n + m); Python's built-in in on strings is fast in practice.

Python Subtree check: brute force and serialization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The leading comma in to_text matters. Without it, a tree with value 12 could match a subtree with value 2 inside the text. The no case shows why the # markers matter too: node 2 has an extra child there, and the markers make that visible in the text. The tricky case is a single leaf, which really does occur in big.

Problem 8: Is it a sum tree?

A sum tree is a binary tree where every non-leaf node holds the sum of all values in its left and right subtrees (an empty subtree counts as 0, and a leaf is always fine). The naive check recomputes subtree sums at every node and costs O(nยฒ) on a skewed tree. Return two things from each call, whether the subtree is valid and its total, and every node is handled once: O(n).

Python Check for a sum tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This "return a pair from the recursion" pattern is the same one used for the diameter and for checking whether a tree is balanced.

Complexity summary

Problem Brute force Better
Diameter O(n^2) worst O(n) one pass
LCA two paths, O(n) one recursion O(n); BST: O(h)
Count paths with sum O(n^2) worst O(n) with prefix-sum map
Same / symmetric / invert n/a O(n)
Serialize / deserialize n/a O(n)
Subtree O(nยทm) O(n + m) with a linear search

Space is O(h) for the recursion in all of them.

Common mistakes

  • Treating a one-child node as a leaf in path-sum questions.
  • Returning the answer from the helper when it should return the height. Diameter needs two things: pass up the height, record the answer on the side.
  • Forgetting that a node is its own descendant in LCA.
  • Comparing values when the problem means identity (node is p versus node.val == p.val).
  • Serializing without markers, which makes different trees produce the same string.
  • Forgetting to undo the prefix-sum count when leaving a node: sums from sibling branches leak into each other.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is the one-pass diameter solution O(n) while the brute-force solution can be O(n^2)?

    The brute force calls a full height computation at every node. The one-pass version returns the height from the recursion and updates the best path at the same time.
  2. 2. In a BST, the LCA of keys 2 and 8 is searched starting at root 6. What is returned?

    2 is smaller and 8 is larger than 6, so they are on different sides of 6 and 6 is the split point.
  3. 3. In the recursive LCA function, what does it mean if both left and right results are not None?

    Each non-empty result means one of the targets was found in that subtree, so the current node is the lowest node containing both.
  4. 4. Why does a serialization of a binary tree need markers for missing children?

    For example, a single left child and a single right child both give the preorder values 1, 2. The markers record where each subtree ends.
  5. 5. In the prefix-sum path counting solution, why do we decrement seen[running] when leaving a node?

    Only prefixes on the current root-to-node path may start a downward path that ends at the current node.

Summary

  • Most tree problems pass information up (heights, counts, found-flags) or down (remaining sum, valid range) a single recursion.
  • Diameter: return the height, track left + right + 2 at every node; the longest path need not pass through the root.
  • LCA: the node where p and q are found in different subtrees; in a BST just compare against the node's key.
  • Path sums: subtract down to a leaf; for arbitrary downward paths, use a prefix-sum dictionary and undo on exit.
  • Same and symmetric trees are pair-of-nodes recursions (mirror compares left with right).
  • Serialize with preorder plus a marker for every empty child; the subtree check can reuse serialization.
  • Self-balancing trees come next: AVL trees.

Next: Self-Balancing Trees: AVL