← Back to Blog
FAANG / MAANG Interview Prep

Top 10 Binary Tree Questions & C++ Solutions

Detailed breakdown of the most frequently asked Binary Tree algorithms at Meta, Google, Amazon, Microsoft, and Netflix. Includes step-by-step intuition, Dry Run diagrams, and clean C++ implementations.

Binary Tree LeetCode Top 100 C++ FAANG Prep DFS & BFS

Table of Contents

1. LC 236 – Lowest Common Ancestor 2. LC 124 – Max Path Sum 3. LC 297 – Serialize & Deserialize 4. LC 863 – All Nodes Distance K 5. LC 987 – Vertical Order Traversal 6. LC 437 – Path Sum III 7. LC 114 – Flatten Binary Tree 8. LC 105 – Construct Tree from Traversals 9. LC 662 – Maximum Width of Tree 10. LC 2385 – Time for Tree to Be Infected

1. LC 236 – Lowest Common Ancestor of a Binary Tree Medium

Companies: Meta, Amazon, Microsoft, Google

Problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes p and q.

Intuition & Diagram

Using Post-Order DFS traversal, recursively explore left and right subtrees. If a node matches p or q, return it. If both left and right return non-null pointers, the current node is the LCA.

3 <-- LCA (Returns 3 because left has 5 and right has 1) / \ 5 1 / \ 6 2 p=5, q=1 => LCA is 3

C++ Code

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        
        if (left && right) return root;
        return left ? left : right;
    }
};
Time: O(N)
Space: O(H) recursion stack

2. LC 124 – Binary Tree Maximum Path Sum Hard

Companies: Meta, Amazon, Google

Problem: Find the maximum path sum in a binary tree. A path is defined as any sequence of nodes following parent-child connections.

Intuition & Diagram

For each node, compute the max path extending downwards into the left and right subtrees. Ignore negative contributions (clamp to 0). The max path passing through the current node as a root curve is left + right + root->val.

-10 / \ 9 20 / \ 15 7 Max Path = 15 + 20 + 7 = 42

C++ Code

class Solution {
    int maxSum = INT_MIN;
    int maxGain(TreeNode* node) {
        if (!node) return 0;
        int leftGain = max(maxGain(node->left), 0);
        int rightGain = max(maxGain(node->right), 0);
        
        int currentPath = node->val + leftGain + rightGain;
        maxSum = max(maxSum, currentPath);
        
        return node->val + max(leftGain, rightGain);
    }
public:
    int maxPathSum(TreeNode* root) {
        maxGain(root);
        return maxSum;
    }
};
Time: O(N)
Space: O(H)

3. LC 297 – Serialize and Deserialize Binary Tree Hard

Companies: Meta, Google, Uber

Problem: Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree.

Intuition & Diagram

Use Pre-Order Traversal (Root-Left-Right) with # representing null nodes and commas separating values. Deserialization uses a stringstream queue to rebuild the tree recursively.

1 / \ 2 3 => Encoded String: "1,2,#,#,3,4,#,#,5,#,#" / \ 4 5

C++ Code

class Codec {
public:
    string serialize(TreeNode* root) {
        if (!root) return "#,";
        return to_string(root->val) + "," + serialize(root->left) + serialize(root->right);
    }

    TreeNode* deserialize(string data) {
        stringstream ss(data);
        return buildTree(ss);
    }

private:
    TreeNode* buildTree(stringstream& ss) {
        string val;
        getline(ss, val, ',');
        if (val == "#") return nullptr;
        
        TreeNode* root = new TreeNode(stoi(val));
        root->left = buildTree(ss);
        root->right = buildTree(ss);
        return root;
    }
};
Time: O(N)
Space: O(N)

4. LC 863 – All Nodes Distance K in Binary Tree Medium

Companies: Amazon, Meta, Netflix

Problem: Return an array of values of all nodes that have a distance k from the target node.

Intuition & Diagram

Convert the binary tree into an undirected graph by tracking parent pointers using a hash map. Perform a Breadth-First Search (BFS) starting from the target node up to radial depth k.

Target = 5, K = 2 3 / \ 5* 1 => BFS outwards: Level 1 -> {3, 6, 2} / \ / \ Level 2 -> {7, 4, 1} (Result: [7, 4, 1]) 6 2 0 8 / \ 7 4

C++ Code

class Solution {
    unordered_map parent;
    void markParents(TreeNode* root) {
        queue q;
        q.push(root);
        while(!q.empty()){
            TreeNode* curr = q.front(); q.pop();
            if(curr->left) { parent[curr->left] = curr; q.push(curr->left); }
            if(curr->right) { parent[curr->right] = curr; q.push(curr->right); }
        }
    }
public:
    vector distanceK(TreeNode* root, TreeNode* target, int k) {
        markParents(root);
        unordered_map visited;
        queue q;
        q.push(target);
        visited[target] = true;
        int dist = 0;
        
        while(!q.empty()){
            if(dist++ == k) break;
            int size = q.size();
            for(int i = 0; i < size; i++){
                TreeNode* curr = q.front(); q.pop();
                if(curr->left && !visited[curr->left]) { q.push(curr->left); visited[curr->left] = true; }
                if(curr->right && !visited[curr->right]) { q.push(curr->right); visited[curr->right] = true; }
                if(parent[curr] && !visited[parent[curr]]) { q.push(parent[curr]); visited[parent[curr]] = true; }
            }
        }
        
        vector res;
        while(!q.empty()){ res.push_back(q.front()->val); q.pop(); }
        return res;
    }
};
Time: O(N)
Space: O(N)

5. LC 987 – Vertical Order Traversal of a Binary Tree Hard

Companies: Meta, Amazon, Bloomberg

Problem: Return the vertical order traversal of nodes in a binary tree from left to right, ordered top to bottom, with overlapping nodes sorted by value.

Intuition & Diagram

Assign coordinates (col, row) to each node. Use BFS with a multiset structure map>> to keep node coordinates automatically sorted.

col: -1 0 1 3 (0,0) / \ (1,-1)9 20 (1,1) / \ (2,0) 15 7 (2,2) Result: [[9], [3, 15], [20], [7]]

C++ Code

class Solution {
public:
    vector> verticalTraversal(TreeNode* root) {
        map>> nodes;
        queue>> q;
        q.push({root, {0, 0}});
        
        while(!q.empty()) {
            auto p = q.front(); q.pop();
            TreeNode* node = p.first;
            int x = p.second.first, y = p.second.second;
            nodes[x][y].insert(node->val);
            
            if(node->left) q.push({node->left, {x - 1, y + 1}});
            if(node->right) q.push({node->right, {x + 1, y + 1}});
        }
        
        vector> ans;
        for(auto& p : nodes) {
            vector col;
            for(auto& q : p.second) {
                col.insert(col.end(), q.second.begin(), q.second.end());
            }
            ans.push_back(col);
        }
        return ans;
    }
};
Time: O(N log N)
Space: O(N)

6. LC 437 – Path Sum III Medium

Companies: Amazon, Microsoft, Target

Problem: Find the number of paths in a binary tree where the sum of node values along the path equals targetSum.

Intuition & Diagram

Use a Prefix Sum Hash Map combined with DFS traversal. If currentSum - targetSum exists in the map, it indicates a valid path segment ending at the current node.

10 (Prefix sum: 10) / 5 (Prefix sum: 15) Target = 8 / 3 (Prefix sum: 18) -> 18 - 8 = 10 (Found in Hash Map! Path: 5 -> 3)

C++ Code

class Solution {
    unordered_map prefixMap;
    int count = 0;
    
    void dfs(TreeNode* node, long long currSum, int target) {
        if (!node) return;
        currSum += node->val;
        
        if (prefixMap.find(currSum - target) != prefixMap.end()) {
            count += prefixMap[currSum - target];
        }
        
        prefixMap[currSum]++;
        dfs(node->left, currSum, target);
        dfs(node->right, currSum, target);
        prefixMap[currSum]--; // Backtrack
    }
public:
    int pathSum(TreeNode* root, int targetSum) {
        prefixMap[0] = 1;
        dfs(root, 0, targetSum);
        return count;
    }
};
Time: O(N)
Space: O(H)

7. LC 114 – Flatten Binary Tree to Linked List Medium

Companies: Meta, Microsoft, Adobe

Problem: Flatten the tree into a linked list in-place using pre-order traversal order.

Intuition & Diagram

Morris Traversal concept: For any node with a left child, find its in-order predecessor (rightmost node in the left subtree), connect its right pointer to node->right, then shift node->left to node->right.

1 1 / \ \ 2 5 => 2 / \ \ \ 3 4 6 3 ... -> 6

C++ Code

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* curr = root;
        while (curr) {
            if (curr->left) {
                TreeNode* prev = curr->left;
                while (prev->right) prev = prev->right;
                
                prev->right = curr->right;
                curr->right = curr->left;
                curr->left = nullptr;
            }
            curr = curr->right;
        }
    }
};
Time: O(N)
Space: O(1) auxiliary

8. LC 105 – Construct Binary Tree from Preorder and Inorder Traversal Medium

Companies: Amazon, Google, Microsoft

Problem: Given preorder and inorder traversal arrays, construct and return the binary tree.

Intuition & Diagram

The first element of preorder is always the root. Locate this root in the inorder array using a hash map to determine left and right subtrees sizes, then construct recursively.

Preorder = [3, 9, 20, 15, 7] (3 is Root) Inorder = [9, |3|, 15, 20, 7] (Left subtree: [9], Right subtree: [15, 20, 7])

C++ Code

class Solution {
    unordered_map inMap;
    TreeNode* build(vector& pre, int preStart, int preEnd, 
                    vector& in, int inStart, int inEnd) {
        if (preStart > preEnd || inStart > inEnd) return nullptr;
        
        TreeNode* root = new TreeNode(pre[preStart]);
        int inRoot = inMap[root->val];
        int numsLeft = inRoot - inStart;
        
        root->left = build(pre, preStart + 1, preStart + numsLeft, in, inStart, inRoot - 1);
        root->right = build(pre, preStart + numsLeft + 1, preEnd, in, inRoot + 1, inEnd);
        return root;
    }
public:
    TreeNode* buildTree(vector& preorder, vector& inorder) {
        for(int i = 0; i < inorder.size(); i++) inMap[inorder[i]] = i;
        return build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
};
Time: O(N)
Space: O(N)

9. LC 662 – Maximum Width of Binary Tree Medium

Companies: Google, Amazon, Bloomberg

Problem: Find the maximum width of a binary tree (maximum number of nodes between the leftmost and rightmost non-null nodes at any level).

Intuition & Diagram

Assign heap-like indices to nodes (Left child: 2*i, Right child: 2*i + 1). To prevent integer overflow, normalize indices by subtracting the level's minimum index at each BFS layer.

1 (idx:0) / \ 3 2 (Level width: 2 - 1 + 1 = 2) / \ \ 5 3 9 (indices: 0, 1, 3 -> Width = 3 - 0 + 1 = 4)

C++ Code

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        unsigned long long maxWidth = 0;
        queue> q;
        q.push({root, 0});
        
        while (!q.empty()) {
            int size = q.size();
            unsigned long long minIdx = q.front().second;
            unsigned long long first = 0, last = 0;
            
            for (int i = 0; i < size; i++) {
                unsigned long long currIdx = q.front().second - minIdx;
                TreeNode* node = q.front().first;
                q.pop();
                
                if (i == 0) first = currIdx;
                if (i == size - 1) last = currIdx;
                
                if (node->left) q.push({node->left, 2 * currIdx + 1});
                if (node->right) q.push({node->right, 2 * currIdx + 2});
            }
            maxWidth = max(maxWidth, last - first + 1);
        }
        return maxWidth;
    }
};
Time: O(N)
Space: O(N)

10. LC 2385 – Amount of Time for Binary Tree to Be Infected Medium

Companies: Amazon, Google

Problem: Return the number of minutes needed for the entire tree to be infected starting from a given target node value.

Intuition & Diagram

Convert the binary tree to an adjacency graph or compute depth relative to the infection node using DFS. The infection spreads 1 edge per minute, equivalent to finding the maximum distance from the target node.

1 (t=2) / \ (t=1) 5 3 (t=3) \ \ (t=0)[4] 10 (t=4) -> Total Time = 4

C++ Code

class Solution {
    unordered_map> adj;
    void buildGraph(TreeNode* node, TreeNode* parent) {
        if (!node) return;
        if (parent) {
            adj[node->val].push_back(parent->val);
            adj[parent->val].push_back(node->val);
        }
        buildGraph(node->left, node);
        buildGraph(node->right, node);
    }
public:
    int amountOfTime(TreeNode* root, int start) {
        buildGraph(root, nullptr);
        queue q;
        unordered_set visited;
        
        q.push(start);
        visited.insert(start);
        int time = -1;
        
        while (!q.empty()) {
            time++;
            int size = q.size();
            while (size--) {
                int curr = q.front(); q.pop();
                for (int neighbor : adj[curr]) {
                    if (!visited.count(neighbor)) {
                        visited.insert(neighbor);
                        q.push(neighbor);
                    }
                }
            }
        }
        return time;
    }
};
Time: O(N)
Space: O(N)