Practice Problems & Solutions

This is it. You've mastered the theory, implementation, and real-world applications. Now it's time to put your knowledge to the test and think like a software engineer. This module is dedicated to solving classic tree coding interview questions.

For each problem, we will follow a structured approach:

1. The Problem: A clear statement of the goal.
2. The Logic: An intuitive, step-by-step plan to solve it.
3. The Code: A clean and efficient Java solution.

Try to solve each problem on your own before looking at the solution. This practice is the single most effective way to prepare for interviews. Let's begin!

1. Find the Height of a Binary Tree

The Problem: Given the root of a binary tree, write a function to find its height. The height is the number of edges on the longest path from the root node down to a leaf node.

The Logic: This is a classic problem solved elegantly with recursion.

• The height of an empty tree (null) is -1 (as there are no nodes or edges).
• The height of a tree with a single node is 0.
• For any other node, its height is 1 + the maximum of the heights of its left and right subtrees. We add 1 to account for the edge connecting the current node to its tallest child's subtree.

The Code:

public int findHeight(TreeNode root) {

// Base Case: An empty tree has a height of -1

if (root == null) {

return -1;

}

// Recursively find the height of the left and right subtrees

int leftHeight = findHeight(root.left);

int rightHeight = findHeight(root.right);

// The height of the tree is 1 + the max of the two subtrees

return 1 + Math.max(leftHeight, rightHeight);

}

Complexity: Time is O(n) as we must visit every node. Space is O(h) (height of the tree) for the recursion stack.

2. Check if Two Trees are Identical

The Problem: Given the roots of two binary trees, p and q, write a function to check if they are structurally identical and have the same node values.

The Logic: We can solve this by traversing both trees simultaneously.

• Base Cases:
  • If both nodes p and q are null, they are identical at this position. Return true.
  • If one is null but the other isn't, or if their data values don't match, they are not identical. Return false.
• Recursive Step: If the current nodes are valid and equal, the two trees are identical only if (their left subtrees are identical) AND (their right subtrees are identical).

The Code:

public boolean isSameTree(TreeNode p, TreeNode q) {

// If both are null, they are identical

if (p == null && q == null) {

return true;

}

// If one is null or their values are different, they are not identical

if (p == null || q == null || p.data != q.data) {

return false;

}

// Recursively check the left and right subtrees

return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

}

Complexity: Time is O(n) (where n is the number of nodes in the smaller tree). Space is O(h).

3. Level Order Traversal (List of Lists)

The Problem: This is a common interview variation of BFS. Given the root of a binary tree, return its nodes' values grouped by level, as a list of lists.

Example: For the tree in our previous modules, the output should be [[8], [3, 10], [1, 6, 14]].

The Logic: We use a standard BFS with a queue. The trick is to know how many nodes are in the current level so we can group them.

1. Initialize a queue and add the root.
2. While the queue is not empty:
   • Get the current size of the queue. This is the number of nodes in the current level.
   • Create a new list for the current level's values.
   • Loop that many times (for each node in the level): dequeue a node, add its value to the level's list, and enqueue its children.
   • Add the level's list to the final result list.

The Code:

import java.util.*;

public List<List<Integer>> levelOrder(TreeNode root) {

List<List<Integer>> result = new ArrayList<>();

if (root == null) {

return result;

}

Queue<TreeNode> queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

int levelSize = queue.size();

List<Integer> currentLevel = new ArrayList<>();

for (int i = 0; i < levelSize; i++) {

TreeNode currentNode = queue.poll();

currentLevel.add(currentNode.data);

if (currentNode.left != null) {

queue.add(currentNode.left);

}

if (currentNode.right != null) {

queue.add(currentNode.right);

}

}

result.add(currentLevel);

}

return result;

}

Complexity: Time is O(n). Space is O(w), where w is the maximum width of the tree.

4. Lowest Common Ancestor (LCA) of a BST

The Problem: Given a Binary Search Tree (BST) and two nodes p and q, find their lowest common ancestor. The LCA is the lowest (deepest) node that has both p and q as descendants.

The Logic: We can leverage the BST property for a highly efficient solution.

1. Start at the root.
2. If both p and q's values are less than the current node's value, the LCA must be in the left subtree.
3. If both p and q's values are greater than the current node's value, the LCA must be in the right subtree.
4. Otherwise, the current node is the "split point" where the paths to p and q diverge. This means the current node is the LCA.

The Code (Iterative):

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

TreeNode current = root;

while (current != null) {

if (p.data > current.data && q.data > current.data) {

// Both are in the right subtree

current = current.right;

} else if (p.data < current.data && q.data < current.data) {

// Both are in the left subtree

current = current.left;

} else {

// We found the split point, this is the LCA

return current;

}

}

return null; // Should not happen in a valid BST with existing nodes

}

Complexity: Time is O(h) (O(log n) on a balanced BST). Space is O(1) for the iterative solution.