Learn DSA Part 9: Trees and Binary Search Trees - Traversals, BST and Interview Problems

Trees are the most asked-about data structure in coding interviews after arrays. They model hierarchies such as file systems, the HTML DOM and organisation charts, and they are the foundation for binary search trees, heaps, tries and many graph ideas. The good news: almost every tree problem is solved with one of two traversals plus the recursive thinking from Part 7.

This is Part 9 of the Learn DSA series. We cover tree vocabulary, the four traversals, how to think recursively about trees, binary search trees, balanced trees, and the classic interview problems. Code is in C++ and Java.

1. Tree vocabulary

A tree is a set of nodes connected by edges with no cycles, starting from a single root. In a binary tree each node has at most two children, left and right.

• Leaf: a node with no children. Depth: number of edges from the root to a node. Height: number of edges on the longest path from a node down to a leaf.
• Full binary tree: every node has 0 or 2 children. Complete: every level is filled except possibly the last, which is filled from the left (this is the shape of a heap, Part 10). Perfect: all levels completely filled.
• Balanced: the heights of the left and right subtrees of every node differ by a small amount, which keeps the height O(log n).

A binary tree with n nodes has height between about log2(n) (balanced) and n - 1 (a chain). Many operations cost O(height), so balance matters.

2. The four traversals

Depth-first traversals go deep before wide and are written naturally with recursion:

• Preorder (node, left, right): copying or serialising a tree.
• Inorder (left, node, right): on a BST this visits values in sorted order.
• Postorder (left, right, node): when a node needs its children's results first, such as deleting a tree or computing heights.

Level order (breadth-first) visits the tree level by level using a queue. It answers questions such as "right side view", "average of each level" or "minimum depth".

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}
};

// Level order traversal: one vector per level. O(n)
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();               // nodes on this level
        vector<int> level;
        for (int i = 0; i < size; 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;
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) { val = v; }
}

// Level order traversal: one list per level. O(n)
static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> res = new ArrayList<>();
    if (root == null) return res;
    Deque<TreeNode> q = new ArrayDeque<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();               // nodes on this level
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

Each traversal visits every node once: O(n) time. Recursive DFS uses O(h) stack space; BFS uses O(w) queue space, where w is the maximum width of the tree.

3. Thinking recursively about trees

Most tree problems follow the same shape: solve the problem for the left subtree, solve it for the right subtree, and combine. Decide what each call returns, handle the empty tree (null) as the base case, and trust the recursion.

// Height (in nodes) of a tree, and diameter (longest path, in edges)
int best = 0;
int height(TreeNode* node) {
    if (!node) return 0;                       // base case
    int l = height(node->left);
    int r = height(node->right);
    best = max(best, l + r);                   // path through this node
    return 1 + max(l, r);                      // what the parent needs
}
int diameterOfBinaryTree(TreeNode* root) {
    best = 0;
    height(root);
    return best;
}

// Height (in nodes) of a tree, and diameter (longest path, in edges)
static int best = 0;
static int height(TreeNode node) {
    if (node == null) return 0;                // base case
    int l = height(node.left);
    int r = height(node.right);
    best = Math.max(best, l + r);              // path through this node
    return 1 + Math.max(l, r);                 // what the parent needs
}
static int diameterOfBinaryTree(TreeNode root) {
    best = 0;
    height(root);
    return best;
}

The diameter example shows a powerful trick: the function returns one thing (the height) to its parent while updating a global answer (the best diameter) on the way. The same trick solves Binary Tree Maximum Path Sum and Longest Univalue Path. Lowest Common Ancestor uses the combine step too: if p and q are found in different subtrees, the current node is the answer.

4. Binary search trees

A binary search tree keeps every value in a node's left subtree smaller than the node and every value in its right subtree larger. That ordering makes search, insert and delete take O(h): at each node you go left or right, like binary search (Part 8). An inorder traversal returns the values sorted.

A common trap when validating a BST is checking only a node against its direct children. The rule applies to the whole subtree, so pass down the allowed range instead:

// Validate a BST by passing down the allowed (low, high) range. O(n)
bool valid(TreeNode* node, long long low, long long high) {
    if (!node) return true;
    if (node->val <= low || node->val >= high) return false;
    return valid(node->left, low, node->val) &&
           valid(node->right, node->val, high);
}
bool isValidBST(TreeNode* root) {
    return valid(root, LLONG_MIN, LLONG_MAX);
}

// Validate a BST by passing down the allowed (low, high) range. O(n)
static boolean valid(TreeNode node, long low, long high) {
    if (node == null) return true;
    if (node.val <= low || node.val >= high) return false;
    return valid(node.left, low, node.val) &&
           valid(node.right, node.val, high);
}
static boolean isValidBST(TreeNode root) {
    return valid(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

Deleting a node with two children replaces its value with its inorder successor (the smallest value in its right subtree) and then deletes that successor. Other favourites: Kth Smallest Element in a BST (inorder and count), converting a sorted array to a balanced BST (pick the middle as the root), and LCA in a BST (go left or right until p and q split).

5. Balanced trees and what to use in practice

If you insert sorted data into a plain BST, it becomes a chain and every operation degrades to O(n). Self-balancing trees such as AVL trees and red-black trees rotate nodes after updates to keep the height O(log n).

Both libraries use red-black trees internally. In interviews you are rarely asked to implement balancing, but you should know why it exists and what it guarantees.

Practice problems

These are classic LeetCode-style problems, listed from easy to hard. For each one, decide what your recursive function returns before writing any code.

1. Maximum Depth of Binary Tree (easy)
2. Invert Binary Tree (easy)
3. Same Tree (easy)
4. Symmetric Tree (easy)
5. Diameter of Binary Tree (easy)
6. Binary Tree Level Order Traversal (medium)
7. Binary Tree Right Side View (medium)
8. Validate Binary Search Tree (medium)
9. Kth Smallest Element in a BST (medium)
10. Lowest Common Ancestor of a Binary Tree (medium)
11. Construct Binary Tree from Preorder and Inorder Traversal (medium)
12. Implement Trie (Prefix Tree) (medium)
13. Binary Tree Maximum Path Sum (hard)
14. Serialize and Deserialize Binary Tree (hard)