Trees: BST and Binary Heap Basics
Binary trees, BST operations, traversals, and heap property for interviews.
12 cards· by GuruOwl
Make a deck like this from your own PDF — free.
Try it- 01Binary tree vs binary search tree (BST)?Binary tree: ≤2 children. BST: left < node < right (ordering invariant) enabling logarithmic search when balanced.bst
- 02Average BST search complexity (balanced-ish)? Worst case?Average O(log n); worst O(n) if skewed like a linked list.bst
- 03Inorder traversal of a BST yields what order?Sorted key order (ascending).traversal
- 04Preorder vs postorder traversal patterns?Preorder: root-left-right. Postorder: left-right-root. Inorder: left-root-right.traversal
- 05What is a binary heap (min-heap)?Complete binary tree where each parent ≤ children; used for priority queues.heap
- 06Heap insert and extract-min complexity?Both O(log n) with bubble up/down; find-min is O(1) at root.heap
- 07Array index for children of node i (0-based heap)?Left = 2i+1, right = 2i+2; parent = floor((i−1)/2).heap
- 08What is a balanced BST example family?AVL, red-black trees — rotations maintain height O(log n).bst
- 09BFS vs DFS on a tree/graph (idea)?BFS: level order (queue). DFS: go deep (stack/recursion).traversal
- 10Full vs complete binary tree (common definitions)?Full: every node has 0 or 2 children. Complete: filled level by level left to right (heap shape).trees
- 11What is tree height (common definition)?Longest root-to-leaf path length (edges or nodes — be consistent; interviews often edges).trees
- 12Why heapsort uses a heap?Repeatedly extract max/min in O(log n) → O(n log n) sort in place.heap