Java Trees and graphs
Where the difficulty steps up. Almost everything reduces to a traversal plus something remembered along the way.
3 concepts · 9 interview questions
What this topic covers
Every concept in trees and graphs, and the questions each one gets asked as. Where a question links, it has a full write-up.
Tree traversal
Depth-first in three orders, or breadth-first level by level. The order chosen usually is the answer to the problem.
- Print a binary tree level by level.
- In-order, pre-order and post-order — when does each matter?
- Find the lowest common ancestor of two nodes.
Binary search trees and balance
Ordered structure giving logarithmic search, provided it stays balanced. Unbalanced, it degrades to a linked list.
- How do you check whether a tree is a valid BST?
- What is a balanced tree, and why does it matter?
- Where does the JDK use a red-black tree?
Graph traversal and shortest paths
Breadth-first finds the fewest edges; depth-first explores a branch fully. Both need a visited set or they do not terminate.
- BFS or DFS — how do you choose?
- Detect a cycle in a directed graph.
- How would you order tasks with dependencies?