DSA interview questions and answers

A binary tree gives each node at most two children with no ordering.

Inorder is left-root-right, preorder is root-left-right, and postorder is left-right-root.

Height is 1 plus the max of left and right subtree heights, with empty as -1 or 0 depending on the convention you state.

BFS with a queue: start from the root and enqueue children as you dequeue parents.

From the root, go left if the target is smaller and right if it is larger, until you hit the node or null.

Walk the same search path until a null child, then attach a new node there, rejecting duplicates if the tree forbids them.

The BST invariant means every left key is smaller and every right key is larger, so left-root-right emits keys in order.

A binary heap is a complete binary tree stored in an array with parent-child index math.

Keep a min-heap of size k: push each number and pop when the heap grows past k so the root is the kth largest.

BFS explores level by level and finds shortest paths in unweighted graphs, using a queue.

An adjacency list stores neighbors per vertex: O(V+E) space and fast iteration over edges, best for sparse graphs.

Iterate vertices

Naive recursion is exponential because it recomputes subproblems.

The number of ways to reach n is ways(n-1) plus ways(n-2), the same recurrence as Fibonacci.

Taking the largest coin that does not exceed the remainder is optimal for canonical systems like US coins.

Sort activities by finish time and repeatedly pick the next one that starts after the last chosen finish.

Sort greed sizes and cookie sizes, then walk both with two pointers, assigning the smallest cookie that satisfies the current child.

Merge sort always splits and merges in O(n log n) time and uses O(n) extra space for the merge buffers.

Pick a pivot, partition smaller keys left and larger right, then recurse.

Stable sorts keep equal keys in their original relative order.