Binary Tree
A binary tree is a tree where each node has at most two children, usually called left and right.
Binary Search Tree
A BST is a binary tree with an ordering rule: left subtree keys are smaller than the node key, and right subtree keys are greater. Each subtree must also be a BST.
Balanced BST operations are usually O(log n). An unbalanced BST can degrade to O(n).
Stack
A stack is LIFO. Use cases include undo, expression parsing, DFS, and parenthesis matching.
Queue
A queue is FIFO. Use cases include request processing, BFS, and scheduling.
Interview Scenario Practice
Scenario 1: Parentheses Matching
Scenario: You need to validate whether brackets are balanced.
Strong answer: Use a stack. Push opening brackets and pop when matching closing brackets appear.
Why it works: The most recent unmatched opening bracket must be closed first, which is LIFO behavior.
Common mistake: Using a queue, which would check brackets in FIFO order and break nested cases.
Scenario 2: Level Order Traversal
Scenario: You need to print a binary tree level by level.
Strong answer: Use BFS with a queue. Enqueue the root, then repeatedly dequeue a node and enqueue its children.
Why it works: A queue preserves level order because nodes are processed in arrival order.
Common mistake: Using DFS and expecting it to naturally produce level order.
Scenario 3: BST Search Became Slow
Scenario: A BST search is taking O(n) in production-like tests.
Strong answer: The tree may be unbalanced. A balanced BST gives O(log n), while a skewed tree behaves like a linked list.
Why it works: BST performance depends on height.
Common mistake: Saying every BST operation is always O(log n) without mentioning balance.