Trees & Binary Search Trees
Master tree data structures — binary trees, BST operations, tree traversals, balanced trees, and heap implementations.
55 min•By Priygop Team•Last updated: Feb 2026
Binary Tree & BST
- Binary Tree: Each node has at most 2 children (left, right). struct TreeNode { int data; struct TreeNode *left, *right; }. Foundation for many advanced structures
- BST Property: Left subtree values < node < right subtree values. Enables O(log n) search, insert, delete on balanced trees. Degenerates to O(n) if unbalanced
- Insertion: Compare with current node — go left if smaller, right if larger. Insert at the first NULL position. O(h) where h is tree height
- Deletion: Three cases — leaf node (just remove), one child (replace with child), two children (replace with inorder successor/predecessor, then delete that)
- Search: Compare value with current node — match found, go left if smaller, go right if larger, NULL means not found. O(log n) average
- Inorder Predecessor/Successor: Predecessor = rightmost node in left subtree. Successor = leftmost node in right subtree. Used in deletion and range queries
Tree Traversals
- Inorder (Left-Root-Right): For BST, produces sorted output. void inorder(Node* root) { if (root) { inorder(root->left); printf(root->data); inorder(root->right); } }
- Preorder (Root-Left-Right): Used to create a copy of the tree, serialize/deserialize trees, and build expression trees from prefix notation
- Postorder (Left-Right-Root): Used to delete a tree (delete children before parent), evaluate expression trees, and calculate directory sizes
- Level Order (BFS): Use a queue — enqueue root, dequeue and process, enqueue children. Visits nodes level by level. Used for finding tree width, shortest path
- Morris Traversal: Inorder traversal without recursion or stack — uses threaded binary tree concept. O(1) space, O(n) time. Modifies tree temporarily
- Binary Heap: Complete binary tree with heap property (max-heap: parent ≥ children). Array representation: left child at 2i+1, right at 2i+2, parent at (i-1)/2