Navigation

DSA trees 11 min read

Tree Exercises: Answer Sheet & Worked Solutions

This is the answer sheet for the tree exercises. Each solution gives the key idea, the optimal complexity, the code in all four languages (use the switcher), and a common pitfall. Try the problems first — then check your work here. All solutions use the standard TreeNode.

Q1. Maximum depth of a binary tree

Idea: A tree’s depth is 1 + the deeper of its two subtrees, with an empty subtree counting as 0. This is the height computation expressed top-down.

Complexity: O(n) time, O(h) space for recursion.

int maxDepth(TreeNode* root) {
    if (root == nullptr) return 0;
    return 1 + std::max(maxDepth(root->left), maxDepth(root->right));
}

int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

function maxDepth(root) {
  if (root === null) return 0;
  return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

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

Pitfall: Returning 0 for a leaf instead of 1. A single node has depth 1; only the empty tree is 0.

Q2. Count the leaf nodes

Idea: A leaf has no children. Recurse: an empty node contributes 0, a leaf contributes 1, and an internal node contributes the sum of its subtrees’ leaf counts.

Complexity: O(n) time, O(h) space.

int countLeaves(TreeNode* root) {
    if (root == nullptr) return 0;
    if (root->left == nullptr && root->right == nullptr) return 1;
    return countLeaves(root->left) + countLeaves(root->right);
}

int countLeaves(TreeNode root) {
    if (root == null) return 0;
    if (root.left == null && root.right == null) return 1;
    return countLeaves(root.left) + countLeaves(root.right);
}

function countLeaves(root) {
  if (root === null) return 0;
  if (root.left === null && root.right === null) return 1;
  return countLeaves(root.left) + countLeaves(root.right);
}

def count_leaves(root):
    if root is None:
        return 0
    if root.left is None and root.right is None:
        return 1
    return count_leaves(root.left) + count_leaves(root.right)

Pitfall: Forgetting the empty-tree base case and dereferencing a null child.

Q3. Invert a binary tree

Idea: Swap every node’s left and right children, then recurse into both. The swap can happen before or after the recursive calls — both work.

Complexity: O(n) time, O(h) space.

TreeNode* invert(TreeNode* root) {
    if (root == nullptr) return nullptr;
    std::swap(root->left, root->right);
    invert(root->left);
    invert(root->right);
    return root;
}

TreeNode invert(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invert(root.left);
    invert(root.right);
    return root;
}

function invert(root) {
  if (root === null) return null;
  [root.left, root.right] = [root.right, root.left];
  invert(root.left);
  invert(root.right);
  return root;
}

def invert(root):
    if root is None:
        return None
    root.left, root.right = root.right, root.left
    invert(root.left)
    invert(root.right)
    return root

Pitfall: Swapping the return values of the recursive calls but not the actual child pointers. Swap the children themselves.

Q4. Are two trees identical?

Idea: Two trees are the same if their roots match and their left subtrees match and their right subtrees match — a direct structural recursion. Both null → equal; one null → unequal.

Complexity: O(n) time, O(h) space.

bool sameTree(TreeNode* p, TreeNode* q) {
    if (p == nullptr && q == nullptr) return true;
    if (p == nullptr || q == nullptr) return false;
    return p->val == q->val
        && sameTree(p->left, q->left)
        && sameTree(p->right, q->right);
}

boolean sameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;
    return p.val == q.val
        && sameTree(p.left, q.left)
        && sameTree(p.right, q.right);
}

function sameTree(p, q) {
  if (p === null && q === null) return true;
  if (p === null || q === null) return false;
  return p.val === q.val
      && sameTree(p.left, q.left)
      && sameTree(p.right, q.right);
}

def same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    return (p.val == q.val
            and same_tree(p.left, q.left)
            and same_tree(p.right, q.right))

Pitfall: Checking values before handling the null cases — comparing p.val when p is null crashes. Handle both-null and one-null first.

Q5. Validate a binary search tree

Idea: A node alone can’t tell you it’s valid — you need the allowed (low, high) range it must fall in, narrowed as you descend. Going left tightens the upper bound; going right tightens the lower bound.

Complexity: O(n) time, O(h) space.

bool isValid(TreeNode* node, long low, long high) {
    if (node == nullptr) return true;
    if (node->val <= low || node->val >= high) return false;
    return isValid(node->left, low, node->val)
        && isValid(node->right, node->val, high);
}
bool isValidBST(TreeNode* root) { return isValid(root, LONG_MIN, LONG_MAX); }

boolean isValid(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return isValid(node.left, low, node.val)
        && isValid(node.right, node.val, high);
}
boolean isValidBST(TreeNode root) {
    return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

function isValidBST(root, low = -Infinity, high = Infinity) {
  if (root === null) return true;
  if (root.val <= low || root.val >= high) return false;
  return isValidBST(root.left, low, root.val)
      && isValidBST(root.right, root.val, high);
}

def is_valid_bst(root, low=float("-inf"), high=float("inf")):
    if root is None:
        return True
    if root.val <= low or root.val >= high:
        return False
    return (is_valid_bst(root.left, low, root.val)
            and is_valid_bst(root.right, root.val, high))

Pitfall: Only comparing a node with its immediate children. A value can satisfy its parent yet violate an ancestor — the range bounds catch that.

Q6. Binary tree level-order traversal

Idea: Breadth-first with a queue. At the start of each loop, the queue holds exactly one full level, so snapshot its size and dequeue that many nodes into the current level’s list.

Complexity: O(n) time, O(n) space (the widest level).

std::vector<std::vector<int>> levelOrder(TreeNode* root) {
    std::vector<std::vector<int>> res;
    if (root == nullptr) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int n = q.size();
        std::vector<int> level;
        for (int i = 0; i < n; i++) {
            TreeNode* node = q.front(); q.pop();
            level.push_back(node->val);
            if (node->left)  q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level);
    }
    return res;
}

List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
        int n = q.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null)  q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        res.add(level);
    }
    return res;
}

function levelOrder(root) {
  const res = [];
  if (root === null) return res;
  let q = [root];
  while (q.length > 0) {
    const level = [], next = [];
    for (const node of q) {
      level.push(node.val);
      if (node.left)  next.push(node.left);
      if (node.right) next.push(node.right);
    }
    res.push(level);
    q = next;
  }
  return res;
}

from collections import deque

def level_order(root):
    res = []
    if root is None:
        return res
    q = deque([root])
    while q:
        n = len(q)
        level = []
        for _ in range(n):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)
    return res

Pitfall: Reading q.size() inside the inner loop after enqueuing children — capture the level size once before the loop.

Q7. Lowest common ancestor in a BST

Idea: Use the ordering. If both values are smaller than the current node, go left; if both larger, go right; the moment they split (or one equals the node), you’re at the LCA.

Complexity: O(h) time → O(log n) balanced, O(1) extra space.

int lcaBST(TreeNode* root, int p, int q) {
    while (root != nullptr) {
        if (p < root->val && q < root->val)      root = root->left;
        else if (p > root->val && q > root->val) root = root->right;
        else return root->val;
    }
    return -1; // not found (p or q absent)
}

int lcaBST(TreeNode root, int p, int q) {
    while (root != null) {
        if (p < root.val && q < root.val)      root = root.left;
        else if (p > root.val && q > root.val) root = root.right;
        else return root.val;
    }
    return -1; // not found (p or q absent)
}

function lcaBST(root, p, q) {
  while (root !== null) {
    if (p < root.val && q < root.val)      root = root.left;
    else if (p > root.val && q > root.val) root = root.right;
    else return root.val;
  }
  return -1; // not found (p or q absent)
}

def lca_bst(root, p, q):
    while root is not None:
        if p < root.val and q < root.val:
            root = root.left
        elif p > root.val and q > root.val:
            root = root.right
        else:
            return root.val
    return -1  # not found (p or q absent)

Pitfall: Using the general O(n) binary-tree algorithm here. It works, but it throws away the BST ordering that makes an O(h), O(1)-space solution possible.

That’s the full answer sheet. Back to the tree exercises or continue to heaps.