Trees & BST | Phase 2

Tree Structure & Terminology

4 ← Root / \ 2 7 ← Internal nodes / \ / \ 1 3 6 9 ← Leaves

Root: Top node (4). No parent.

Leaf: Node with no children (1,3,6,9).

Height: Longest path from root to leaf. Here = 2.

Depth: Distance from root to a node.

BST: Left < Root < Right at every node.

Complete: All levels filled (except possibly last).

Node Definition & 4 Traversals

C++
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// INORDER: Left → Root → Right  (gives sorted order in BST)
void inorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorder(root->left, res);
    res.push_back(root->val);
    inorder(root->right, res);
}

// PREORDER: Root → Left → Right  (used for serialization)
void preorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
}

// POSTORDER: Left → Right → Root  (delete nodes safely)
void postorder(TreeNode* root, vector<int>& res) {
    if (!root) return;
    postorder(root->left, res);
    postorder(root->right, res);
    res.push_back(root->val);
}

// LEVEL ORDER: BFS with queue
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        while (sz--) {
            auto 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;
}
    

4 Traversal Orders

Inorder

L → Root → R

1,2,3,4,6,7,9

Gives sorted output in BST

Preorder

Root → L → R

4,2,1,3,7,6,9

Serialization, copy tree

Postorder

L → R → Root

1,3,2,6,9,7,4

Delete tree, evaluate expr

Level Order

BFS level by level

4, 2 7, 1 3 6 9

Shortest path, zigzag

DFS Recursion Template

Most tree problems follow this exact template. Fill in the logic at each node.

C++
// Universal DFS template for tree problems
int dfs(TreeNode* node) {
    // 1. Base case
    if (!node) return 0;  // or false, or INT_MIN, etc.

    // 2. Recurse on children
    int left  = dfs(node->left);
    int right = dfs(node->right);

    // 3. Process current node using children results
    // (this is where the actual logic goes)
    return max(left, right) + 1;   // e.g. height
}
// Every tree DFS problem = fill in steps 1, 2, 3.
// The recursion handles the rest automatically.
    

Interactive: BST Insert

Watch how each value walks down the BST — compare at each node, go left if smaller, right if larger — until an empty slot is found. Highlighted (purple) nodes are the compare path; cyan shows the newly placed node.

Interactive: Four Traversals

Select a traversal order to see the visit sequence on the same 7-node BST. Green = already visited, cyan = currently visiting.

Deeper Understanding

🧠 Under the Hood

A BST is stored as heap-allocated nodes linked by pointers — no contiguous array. Each node takes ~24 bytes (val + two pointers). A perfectly balanced BST of n nodes has height ⌊log₂ n⌋, giving O(log n) search/insert/delete. A skewed BST degrades to O(n). Standard library std::set / std::map use Red-Black trees to enforce O(log n) worst-case balance automatically.

⚖️ When to Use / When NOT to Use

✅ Use BST when you need sorted iteration + O(log n) search/insert/delete

Use std::set/std::map in interviews — they're RB-trees that guarantee balance automatically. Roll your own only if the problem requires custom structure.

✅ Use recursive DFS when the problem has natural sub-tree decomposition

Height, LCA, path sum — anything where result at root depends on results from subtrees. The recursion structure mirrors the tree structure exactly.

✅ Use BFS (level-order) for shortest-path in trees or level-based queries

Minimum depth, right-side view, zigzag level-order — these require processing nodes level by level which DFS cannot do naturally.

❌ Avoid BST when order doesn't matter and keys repeat

Instead: Use unordered_map/unordered_set — O(1) average lookup without the O(log n) overhead of a tree.

❌ Avoid raw BST when input may arrive in sorted order (worst case O(n) height)

Instead: Use a self-balancing tree (AVL, Red-Black) — or just std::set which is already balanced.

🚫 Common Misconceptions

❌ "BST search is always O(log n)"

Only in a balanced BST. A skewed tree (inserting sorted input) becomes a linked list with O(n) search. Validate BST problems often involve this degenerate case.

❌ "Inorder gives sorted output on any binary tree"

Inorder gives sorted output only on a BST. On a generic binary tree, inorder just visits left→root→right with no ordering guarantee.

❌ "You should validate a BST by checking left.val < root < right.val"

This only checks direct children. A correct validation passes down min/max bounds through recursion: every node must be strictly inside (lo, hi) inherited from ancestors.

🎤 Interview Follow-ups

Why does validating a BST need INT_MIN/INT_MAX bounds?

Edge case: a node with value INT_MIN as left child. Comparing node.val < root.val works, but comparing against left.val fails if left is null. Passing numeric bounds handles all edge cases cleanly.

How to do iterative inorder without recursion?

Explicit stack: push all left children, then pop-process-go-right. Exact simulation of the call stack — useful when recursion depth could hit OS limits on a skewed tree.

Why can't std::unordered_set do floor/ceiling queries?

Hash sets have no ordering — elements are bucketed by hash value, not sorted. Floor/ceiling require O(log n) lookup in sorted order — only balanced BSTs (like std::set) support this natively via lower_bound/upper_bound.

Practice Problems

#104Maximum Depth of Binary TreeEasy

Return the maximum depth (number of nodes along the longest root-to-leaf path).

Pattern: DFS. Height of node = 1 + max(height(left), height(right)). Base: null node has height 0.

C++
int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return 1 + max(maxDepth(root->left), maxDepth(root->right));
}
// Time: O(n)  Space: O(h) call stack

#226Invert Binary TreeEasy

Invert a binary tree (mirror it left-right at every node).

Pattern: Swap left and right children, then recurse. Post-order or pre-order both work.

C++
TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}
// Time: O(n)  Space: O(h)

#543Diameter of Binary TreeEasy

Find the length of the longest path between any two nodes (may or may not pass through root).

Pattern: At each node, diameter through it = left_height + right_height. Track global max. Return height to parent.

C++
int res = 0;
int dfs(TreeNode* node) {
    if (!node) return 0;
    int l = dfs(node->left);
    int r = dfs(node->right);
    res = max(res, l + r);    // diameter through this node
    return 1 + max(l, r);     // height returned to parent
}
int diameterOfBinaryTree(TreeNode* root) {
    dfs(root); return res;
}
// Time: O(n)  Space: O(h)

#100Same TreeEasy

Given two binary trees, return true if they are structurally identical with same node values.

Pattern: Both null → equal. One null or values differ → not equal. Recurse on both children.

C++
bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left) &&
           isSameTree(p->right, q->right);
}
// Time: O(n)  Space: O(h)

#102Binary Tree Level Order TraversalMedium

Return values of each level as a list of lists. [[4],[2,7],[1,3,6,9]].

Pattern: BFS with queue. Process all nodes at current level (size of queue), collect, then enqueue children.

C++
vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q; q.push(root);
    while (!q.empty()) {
        int sz = q.size();
        vector<int> level;
        while (sz--) {
            auto n = q.front(); q.pop();
            level.push_back(n->val);
            if (n->left)  q.push(n->left);
            if (n->right) q.push(n->right);
        }
        res.push_back(level);
    }
    return res;
}
// Time: O(n)  Space: O(n)

#235Lowest Common Ancestor of BSTMedium

In a BST, find the lowest common ancestor of nodes p and q.

Pattern: BST property! If both p,q smaller than root → LCA in left. If both larger → LCA in right. Otherwise → root is LCA.

C++
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    while (root) {
        if      (p->val < root->val && q->val < root->val) root = root->left;
        else if (p->val > root->val && q->val > root->val) root = root->right;
        else return root;  // split point = LCA
    }
    return nullptr;
}
// Time: O(h)  Space: O(1)

#98Validate Binary Search TreeMedium

Verify that a binary tree is a valid BST (all left < root < all right, not just direct children).

Pattern: Pass min/max bounds down. Each node must be strictly within (min, max). Initially bounds are (-∞, +∞).

C++
bool valid(TreeNode* node, long lo, long hi) {
    if (!node) return true;
    if (node->val <= lo || node->val >= hi) return false;
    return valid(node->left,  lo, node->val) &&
           valid(node->right, node->val, hi);
}
bool isValidBST(TreeNode* root) {
    return valid(root, LONG_MIN, LONG_MAX);
}
// Time: O(n)  Space: O(h)

#124Binary Tree Maximum Path SumHard

Find the maximum path sum between any two nodes (path may or may not pass through root).

Pattern: At each node, consider: path bends through here (left + node + right). But return to parent only the best branch (can't go both ways up). Track global max separately.

C++
int maxSum = INT_MIN;
int dfs(TreeNode* node) {
    if (!node) return 0;
    int l = max(0, dfs(node->left));   // ignore negatives
    int r = max(0, dfs(node->right));
    maxSum = max(maxSum, l + node->val + r);  // path through here
    return node->val + max(l, r);  // best branch to parent
}
int maxPathSum(TreeNode* root) {
    dfs(root); return maxSum;
}
// Time: O(n)  Space: O(h)

#297Serialize and Deserialize Binary TreeHard

Design algorithm to serialize a tree to string and deserialize back. Any format works.

Pattern: Preorder traversal with null markers. Serialize: preorder with "null" for nulls. Deserialize: recursive — take first token, if null return null, else build node and recurse.

C++
string serialize(TreeNode* root) {
    if (!root) return "N,";
    return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
}
TreeNode* deserHelper(queue<string>& q) {
    string val = q.front(); q.pop();
    if (val == "N") return nullptr;
    TreeNode* node = new TreeNode(stoi(val));
    node->left  = deserHelper(q);
    node->right = deserHelper(q);
    return node;
}
TreeNode* deserialize(string data) {
    queue<string> q;
    stringstream ss(data);
    string token;
    while (getline(ss, token, ',')) q.push(token);
    return deserHelper(q);
}
// Time: O(n)  Space: O(n)

#230Kth Smallest Element in a BSTMedium

Given the root of a BST and integer k, return the kth smallest value (1-indexed) in the tree.

Pattern: Inorder traversal gives sorted order in a BST. Count nodes as you visit them; return the kth one. Can also be done iteratively with an explicit stack.

C++
int res, cnt;
void inorder(TreeNode* node, int k) {
    if (!node) return;
    inorder(node->left, k);
    if (++cnt == k) { res = node->val; return; }
    inorder(node->right, k);
}
int kthSmallest(TreeNode* root, int k) {
    cnt = 0;
    inorder(root, k);
    return res;
}
// Inorder visits BST nodes in sorted ascending order.
// Time: O(H+k)  Space: O(H) where H = tree height

Golden rule: When writing a tree function, think: "What does this function return to its parent?" Once you know that, the recursion writes itself.