Trees and Binary Search Trees Interview Questions for Data Structures and Algorithms

Show answer

The root is the top node with no parent. A leaf has no children. The depth of a node is the number of edges from the root to it, and the height of a node is the number of edges on the longest path down to a leaf; the tree's height is the root's height. In a binary tree each node has at most two children. A tree with n nodes has n minus 1 edges.

What are inorder, preorder, postorder and level order traversals?

Show answer

Inorder visits left subtree, node, then right subtree, and gives sorted order for a BST. Preorder visits node, left, then right, which is useful for copying or serialising a tree. Postorder visits left, right, then node, used for deleting trees or computing subtree results. Level order visits nodes level by level using a queue. All take O(n) time; recursive versions use O(h) stack space.

What is a binary search tree and what is its time complexity?

Show answer

In a BST every node's left subtree contains smaller keys and the right subtree larger keys. Search, insert and delete follow one path from the root, so they take O(h) time, where h is the height. A balanced tree has h about log n, giving O(log n). Inserting sorted data into a plain BST creates a skewed tree that behaves like a linked list with O(n) operations, which is why balanced variants exist.

What is the difference between full, complete and perfect binary trees?

Show answer

In a full binary tree every node has zero or two children. In a complete binary tree every level except possibly the last is completely filled, and the last level is filled from the left, which is exactly the shape of a binary heap and allows array storage. A perfect binary tree has all internal nodes with two children and all leaves at the same level, containing 2 to the power h plus 1, minus 1 nodes.

Write an iterative inorder traversal of a binary tree.

Show answer

def inorder(root): result, stack = [], [] node = root while node or stack: while node: # go as far left as possible stack.append(node) node = node.left node = stack.pop() result.append(node.val) # visit node = node.right # then the right subtree return result # O(n) time, O(h) space; no recursion limit issues

Find the maximum depth of a binary tree.

Show answer

// Java static int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); } // Each node visited once: O(n) time, O(h) stack space. // BFS alternative: count levels while processing the queue level by level.

Tell me about the project you are most proud of.

Show answer

Situation: in college I noticed students struggled to find relevant previous-year questions. Task: build a searchable question bank. Action: I built a small web app with a trie-based autocomplete for topics and an inverted index for keyword search, wrote tests and collected feedback from classmates. Result: over 400 students used it during exams, search stayed under 50 milliseconds, and I learned how data structure choices affect real users.

Compare AVL trees and red-black trees.

Show answer

Both are self-balancing BSTs with O(log n) operations. AVL trees keep the heights of sibling subtrees within one, so they are more strictly balanced and give faster lookups, but need more rotations on insert and delete. Red-black trees allow looser balance using node colours, so updates are cheaper. That is why Java TreeMap and C++ std::map use red-black trees, while AVL suits read-heavy workloads.

What is a trie and where is it used?

Show answer

A trie, or prefix tree, stores strings character by character, with each edge representing a character and a flag marking word ends. Insert and search take O(L) for a word of length L regardless of how many words are stored, and all words sharing a prefix sit under one node. Tries power autocomplete, spell checkers, IP routing with longest prefix match and word search games. Memory use can be high, so compressed tries exist.

How do you find the lowest common ancestor in a BST versus in a general binary tree?

Show answer

In a BST, start at the root: if both values are smaller go left, if both are larger go right, otherwise the current node is the LCA, taking O(h). In a general binary tree, recurse: if the node is null or matches either target, return it; otherwise search both subtrees. If both sides return non-null, the current node is the LCA; else return the non-null side. That takes O(n).

How do DFS and BFS differ in memory use on a tree?

Show answer

DFS uses a stack, either the call stack or an explicit one, holding at most the height of the tree, so O(h) memory: about log n for balanced trees but n for skewed ones. BFS uses a queue holding an entire level, up to about n over 2 nodes in the last level of a complete tree. So DFS is lighter for wide balanced trees, while BFS is natural for shortest paths and level-wise processing.

What is the diameter of a binary tree and how do you compute it efficiently?

Show answer

The diameter is the number of edges on the longest path between any two nodes, which may not pass through the root. Compute it in one postorder traversal: for each node, get the heights of the left and right subtrees, update a global best with left plus right, and return 1 plus the larger height to the parent. This visits each node once, giving O(n) time instead of O(n squared) from recomputing heights.

You must build autocomplete for a search box over one million product names. Which data structure would you use?

Show answer

I would use a trie where each node stores, besides children, the top few most popular completions under that prefix. Then typing a prefix walks L nodes and returns precomputed suggestions instantly, without exploring the whole subtree. Memory can be reduced with a compressed radix trie. For typo tolerance or ranking by many signals, a search engine with prefix indexes is more practical at large scale.

An application needs sorted data with frequent inserts, deletes and range queries such as all orders between two timestamps. Which structure fits?

Show answer

A balanced BST, such as Java TreeMap or a sorted container in Python, gives O(log n) insert and delete and O(log n plus k) range queries using floor, ceiling or subMap operations. A sorted array has fast range queries but O(n) inserts, and a hash map cannot do ranges at all. If the data lives in a database, a B-tree index on the timestamp column solves the same problem.

A teammate's BST validation only checks that each node is greater than its left child and smaller than its right child. Why is that wrong?

Show answer

The BST property applies to entire subtrees, not just direct children. A node deep in the left subtree could be larger than the root and still pass the local check. The correct approach passes a valid range down the recursion: the left child must lie between the lower bound and the node value, the right child between the node value and the upper bound. Alternatively, check that an inorder traversal is strictly increasing.

In a company org chart stored as a tree, how would you find the closest common manager of two employees?

Show answer

This is the lowest common ancestor problem. If each employee stores a parent pointer, collect the ancestors of the first employee in a set and walk up from the second until a match is found, O(h). Without parent pointers, use the recursive LCA on the tree from the CEO, O(n). For many repeated queries on a large chart, preprocess with binary lifting to answer each query in O(log n).

Print the level order traversal of a binary tree, one list per level.

Show answer

from collections import deque def level_order(root): if not root: return [] out, q = [], deque([root]) while q: level = [] for _ in range(len(q)): # process exactly one level node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) out.append(level) return out

Write a function to validate a binary search tree.

Show answer

def is_valid_bst(root, low=float('-inf'), high=float('inf')): if not root: return True if not (low < root.val < high): return False return (is_valid_bst(root.left, low, root.val) and is_valid_bst(root.right, root.val, high)) # Passing bounds checks the whole-subtree property, not just children. # O(n) time, O(h) space.

Find the lowest common ancestor of two nodes in a binary tree.

Show answer

def lca(root, p, q): if root is None or root is p or root is q: return root left = lca(root.left, p, q) right = lca(root.right, p, q) if left and right: # p and q are on different sides return root return left or right # O(n) time, O(h) space; assumes both nodes exist in the tree

Tell me about an interview or exam you failed and what you learned.

Show answer

Situation: I was rejected after a coding round because I could not solve a tree problem in time. Task: understand the gap honestly. Action: I wrote down the question, realised I memorised solutions instead of patterns, and reorganised my practice by patterns such as postorder aggregation and BFS by level, explaining each solution aloud. Result: three months later I cleared a similar round comfortably, and I now review every mistake within a day.

Compare segment trees and Fenwick trees.

Show answer

Both answer range queries with point updates in O(log n). A Fenwick tree, or binary indexed tree, is compact, simple to code and ideal for prefix sums and counts, but supports mainly invertible operations. A segment tree stores an aggregate for each segment, handles any associative operation such as min, max or gcd, and supports range updates with lazy propagation, at the cost of about 4n memory and longer code.

What is a B-tree and why do databases use it for indexes?

Show answer

A B-tree is a balanced search tree where each node holds many keys and has many children, often hundreds. This keeps the tree very shallow, so a lookup among millions of rows touches only three or four nodes. Each node is sized to a disk or memory page, minimising expensive I/O. B+ trees, used by MySQL InnoDB and PostgreSQL, keep all values in linked leaves, making range scans efficient.

A recursive tree traversal crashes on a skewed tree with one million nodes. How do you fix it?

Show answer

A skewed tree has height about n, so recursion needs a million stack frames and overflows. Rewrite the traversal iteratively with an explicit stack stored on the heap, or use Morris traversal, which threads temporary links through the tree to achieve O(1) extra space. If the tree is built by our code, also consider why it is skewed and switch to a self-balancing tree so height stays O(log n).

A game leaderboard with millions of players needs fast score updates and queries like what rank is this player. How would you design it?

Show answer

Sorting on every query is too slow. I would bucket scores and use a Fenwick tree or segment tree over score values, storing how many players have each score; a player's rank is the count of players with higher scores, found in O(log S). Updates move a player between buckets in O(log S). An order-statistic balanced tree also works, and in production Redis sorted sets, built on skip lists, provide this directly.

Serialize a binary tree to a string and deserialize it back.