Trees & Graphs Basics Questions

Understand binary trees, binary search trees, and basic graph concepts. Know tree traversal methods: in-order, pre-order, post-order, and level-order (BFS). Practice DFS and BFS implementations. Know the difference between directed and undirected graphs. Solve medium-difficulty tree and graph problems.

EasyTechnical

21 practiced

Implement iterative pre-order traversal of a binary tree in C++ without recursion. Signature: vector<int> preorderTraversal(TreeNode* root). Explain why a stack is sufficient for preorder and analyze time and space complexity. Example: input [1,null,2,3] should produce [1,2,3].

Sample Answer

Approach:Use an explicit stack to simulate recursion. Pre-order visits root → left → right. At each step, pop a node, record its value, then push its right child (if any) and then its left child (if any). Pushing right before left ensures left is processed next (LIFO). A single stack is sufficient because recursion itself is just an implicit stack of nodes.

cpp

#include <vector>
#include <stack>
using namespace std;

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

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> st;
    st.push(root);

    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        res.push_back(node->val);
        if (node->right) st.push(node->right); // push right first
        if (node->left)  st.push(node->left);  // so left is processed next
    }
    return res;
}

Key points:- Stack models the call stack for recursion; pushing right then left preserves pre-order.- Works for large trees without risking call-stack overflow.

Complexity:- Time: O(n) — each node visited once.- Space: O(h) worst-case O(n) where h is tree height (stack stores path nodes; for skewed tree h = n).

Edge cases:- Empty tree (returns empty vector).- Trees with single child or skewed shape handled correctly.

Alternative:- You can also do a modified iterative approach that walks left children and pushes right children while processing nodes to slightly reduce pushes, but semantics and complexity remain the same. Example input [1,null,2,3] returns [1,2,3].

MediumTechnical

19 practiced

Implement a function in Python to invert a binary tree in-place (swap left and right children of every node). Signature: def invertTree(root) -> TreeNode. Provide a concise recursive solution and an iterative solution using a stack or queue, and discuss complexity and when iterative might be preferred.

Sample Answer

A binary tree can be inverted by swapping each node’s left and right children. Two common approaches: recursive DFS (concise) and iterative using a stack or queue (explicit traversal).

Recursive (concise):

python

def invertTree(root):
    """
    In-place invert binary tree. Returns root.
    """
    if not root:
        return None
    # swap children
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

Iterative (using stack, DFS) — avoids recursion depth limits:

python

def invertTree_iter(root):
    if not root:
        return None
    stack = [root]
    while stack:
        node = stack.pop()
        node.left, node.right = node.right, node.left
        if node.left: stack.append(node.left)
        if node.right: stack.append(node.right)
    return root

Key points:- Time complexity: O(n) — visit each node once.- Space complexity: O(h) where h is tree height (recursion stack or explicit stack). Worst-case O(n) for skewed tree.- Use iterative when tree is very deep (risk of recursion limit/stack overflow) or when you need explicit control over traversal order. Recursive is simpler and idiomatic for balanced trees.

Edge cases: empty tree (None), single-node tree, skewed trees (test for recursion depth).

HardSystem Design

26 practiced

Design a friend-recommendation system for a large social network with 100 million active users and billions of follower/friend edges. Describe the data model for the social graph, storage choices (distributed adjacency lists, graph databases, or key-value stores), algorithms for recommendations (common neighbors, two-hop suggestions, personalized scoring), offline vs online computation, caching strategies, privacy concerns, and how to handle rate limits and scalability for real-time suggestions.

Sample Answer

Requirements & constraints:- 100M active users, billions of edges, low-latency real-time suggestions (<200ms), personalization, privacy controls, eventual consistency acceptable for recommendations.

High-level architecture:- Batch pipeline (offline candidate generation & model training) + Online service (real-time scorer & cache) + Storage layer (graph + metadata) + API layer.

Data model:- Social graph as directed adjacency lists: user_id -> {followers:[], followees:[]} stored as compressed arrays (sorted, delta-encoded).- User features table: user_id -> {profile attrs, engagement, last_active, opt_out_flags}- Interaction logs: time-series edges for recency/weighting.

Storage choices:- Distributed adjacency lists in a key-value store (e.g., RocksDB on distributed nodes, sharded by user_id) for fast fanout reads.- Graph database (e.g., Nebula/JanusGraph) only for analytical/one-off queries; not for 100ms path traversals at scale.- Columnar store / HDFS for offline batch processing.

Recommendation algorithms:- Candidate generation (offline, broad): - Two-hop common neighbors (friends of friends) using mapreduce/graph engine to produce top-N candidates per user. - Co-follow/co-engagement: users who follow similar sets or interact with same content. - Embedding-based nearest neighbors: train node2vec/GraphSAGE embeddings offline; use approximate nearest neighbor (FAISS) to get candidates.- Online scoring (personalized, real-time): - Features: common_neighbor_count, mutual_follow_ratio, recency, interaction_frequency, embedding cosine similarity, popularity, geographic overlap. - Scoring model: lightweight ML model (logistic regression / gradient boosted trees or a small neural net) serving via a low-latency predictor. Apply business rules (privacy, blocked lists).

Offline vs online:- Offline: heavy candidate generation, embedding training, feature aggregation (daily/hourly).- Online: fetch precomputed candidates from cache/kv, compute real-time features (fresh interactions, presence online), run fast scorer, respond in <200ms. If no candidates, fallback to popularity or embedding-NN.

Caching strategies:- Multi-tier cache: - CDN/edge caches for public suggestion pages. - Mid-tier cache (Redis/Memcached) for user -> candidate list (TTL short: minutes). - Local LRU in application servers for hot users.- Cache invalidation: write-through on follow/unfollow events; event-driven invalidation of affected users' caches.

Privacy & safety:- Honor privacy flags and blocked/hidden lists at query time.- Differential privacy/aggregation for analytics.- Rate-limit exposure of mutual connections to prevent enumeration attacks.- Audit logs and moderation filters for abusive accounts.

Rate limits & scalability:- Throttle API requests per user/IP; use token buckets.- Partition graph by user_id for horizontal scaling; replicate hot partitions.- Use fanout-on-read for sparse queries and fanout-on-write for notifications. For recommendations, precompute to avoid heavy fanout at read-time.- Autoscale model-serving pods; use batching for scoring when possible.- Use approximate algorithms (ANN, Bloom filters) to reduce I/O.

Monitoring & metrics:- Track latency p50/p99, click-through rate, acceptance rate, cache hit ratio, recommendation freshness, privacy violations.

Trade-offs:- Precompute reduces latency but increases storage and staleness; online computing gives freshness but higher CPU/IO. Hybrid (precompute + lightweight online re-ranking) balances both.

This design provides low-latency, personalized suggestions at scale while balancing freshness, cost, and privacy.

EasyTechnical

20 practiced

Explain the difference between a general binary tree and a binary search tree (BST). Include precise definitions, structural and ordering invariants, typical operations (search, insert, delete) with average and worst-case time complexity, example node arrangements (for example: [5,3,7] as a small BST and [5,4,3] as a skewed tree), and describe one real-world use case where an ordinary BST is not suitable without balancing.

HardTechnical

21 practiced

Implement an algorithm in C++ to compute the diameter (length of the longest path between any two nodes) of an unrooted tree. Signature: int diameterOfBinaryTree(TreeNode* root). Explain and implement both the two-BFS (or two-DFS) method and a single-pass DFS that computes heights and updates the diameter, and analyze time and space complexity.

Sample Answer

Two approaches: (A) two DFS/BFS passes (find farthest node, then farthest from that node) and (B) single-pass DFS computing heights and updating diameter.

Common TreeNode:

cpp

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

A) Two-DFS (works for any tree; for binary tree we treat edges between parent/child)- Run DFS/BFS from root to find the farthest node A (by distance).- Run DFS/BFS from A to find farthest node B; distance(A,B) is diameter.Time: O(n) (two passes). Space: O(h) recursion or O(n) queue.

cpp

#include <vector>
#include <queue>
#include <unordered_map>

int bfsFarthest(TreeNode* start, TreeNode*& outNode){
    if(!start){ outNode = nullptr; return 0; }
    std::queue<TreeNode*> q;
    std::unordered_map<TreeNode*, int> dist;
    q.push(start); dist[start]=0; TreeNode* last=start;
    while(!q.empty()){
        auto cur = q.front(); q.pop();
        last = cur;
        int d = dist[cur];
        if(cur->left && !dist.count(cur->left)){ dist[cur->left]=d+1; q.push(cur->left); }
        if(cur->right && !dist.count(cur->right)){ dist[cur->right]=d+1; q.push(cur->right); }
        // For unrooted tree, we'd also add parent; here assume binary tree and edges only to children
    }
    outNode = last;
    return dist[last];
}

int diameterOfBinaryTree_twoDFS(TreeNode* root){
    if(!root) return 0;
    TreeNode* a=nullptr;
    bfsFarthest(root, a);
    TreeNode* b=nullptr;
    return bfsFarthest(a, b);
}

B) Single-pass DFS (preferred for binary trees)- At each node, compute leftHeight and rightHeight (max edges to a leaf).- Local path through node = leftHeight + rightHeight.- Global diameter = max(global, local).- Return height = 1 + max(leftHeight, rightHeight) (or 0-based edges; here count edges).

Time: O(n) single traversal. Space: O(h) recursion stack.

cpp

int diameterSingle;
int heightDFS(TreeNode* node){
    if(!node) return 0; // height in edges = 0 for null
    int lh = heightDFS(node->left);
    int rh = heightDFS(node->right);
    diameterSingle = std::max(diameterSingle, lh + rh); // path going through node
    return 1 + std::max(lh, rh);
}

int diameterOfBinaryTree(TreeNode* root){
    diameterSingle = 0;
    heightDFS(root);
    return diameterSingle;
}

Key points:- Use edges count: we returned diameter as number of edges between nodes. If problem expects node count, add +1 when non-zero.- Edge cases: empty tree (0), single node (0 edges), skewed tree (height n-1).- Trade-offs: two-BFS generalizes to arbitrary unrooted trees when you have adjacency lists and is robust; single-pass DFS is simplest and optimal for rooted binary trees.

Unlock Full Question Bank

Get access to hundreds of Trees & Graphs Basics interview questions and detailed answers.

Join thousands of developers preparing for their dream job.