Computer Science · College · BCA, BTech & MCA
Binary Trees & BST: Tree Traversals, Search, Insert & BST Rules
Master hierarchical trees: Binary Trees, Binary Search Trees (BST), Preorder, Inorder, and Postorder traversals, and O(h) search and insertion mechanics.
1Binary Tree Anatomy & Classification
Full sizeBinary Trees & BST: Tree Traversals, Search, Insert & BST Rules
Master hierarchical trees: Binary Trees, Binary Search Trees (BST), Preorder, Inorder, and Postorder traversals, and O(h) search and insertion mechanics.
- 1Subject — Computer Science
- 2Target Audience — BCA, BTech & MCA Students
- 3Topic Core — Traversals, BST Properties & Search Complexity
ABinary Treeis a non-linear hierarchical data structure in which each node hasat most two children, designated as theleft childandright child. The topmost node is called theroot, and nodes with no children areleaves.
Binary Tree Classifications
| Tree Type | Defining Characteristic | Maximum / Minimum Nodes for Height h |
|---|---|---|
| Full Binary Tree | Every node has either 0 or 2 children (no node has only 1 child) | 2h + 1 nodes minimum |
| Complete Binary Tree | All levels are completely filled except possibly the last, which is filled from left to right | Between 2ʰ and 2ʰ⁺¹ - 1 nodes |
| Perfect Binary Tree | All internal nodes have 2 children and all leaf nodes are at the identical depth | Exactly 2ʰ⁺¹ - 1 nodes |
| Balanced Tree (AVL / Red-Black) | Height difference between left and right subtrees (balance factor) is at most 1 | Height is strictly bounded by O(log n) |
Full Binary Tree
- Defining Characteristic
- Every node has either 0 or 2 children (no node has only 1 child)
- Maximum / Minimum Nodes for Height h
- 2h + 1 nodes minimum
Complete Binary Tree
- Defining Characteristic
- All levels are completely filled except possibly the last, which is filled from left to right
- Maximum / Minimum Nodes for Height h
- Between 2ʰ and 2ʰ⁺¹ - 1 nodes
Perfect Binary Tree
- Defining Characteristic
- All internal nodes have 2 children and all leaf nodes are at the identical depth
- Maximum / Minimum Nodes for Height h
- Exactly 2ʰ⁺¹ - 1 nodes
Balanced Tree (AVL / Red-Black)
- Defining Characteristic
- Height difference between left and right subtrees (balance factor) is at most 1
- Maximum / Minimum Nodes for Height h
- Height is strictly bounded by O(log n)
2Tree Traversals (DFS: Inorder, Preorder, Postorder)
Unlike linear data structures, trees can be traversed in several distinct sequential orders usingDepth-First Search (DFS):
- Inorder (Left, Root, Right):Produces elements of a Binary Search Tree instrictly sorted ascending order.
- Preorder (Root, Left, Right):Ideal for creating a clone or serialized copy of the tree.
- Postorder (Left, Right, Root):Ideal for deleting nodes or bottom-up evaluations (e.g., calculating subtree directory sizes or abstract syntax tree evaluations).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder(root):
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def preorder(root):
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def postorder(root):
return postorder(root.left) + postorder(root.right) + [root.val] if root else []
# Build tree: 4
# / \
# 2 5
# / \
# 1 3
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(5))
print("Inorder: ", inorder(root))
print("Preorder: ", preorder(root))Inorder: [1, 2, 3, 4, 5] Preorder: [4, 2, 1, 3, 5]
3Binary Search Tree (BST) Properties & Operations
Definition
Binary Search Tree (BST) Rule — For every node N in the tree: all node keys in N’s left subtree must be strictly less than N.key, and all node keys in N’s right subtree must be strictly greater than N.key.
BST Operations Time Complexity
| Operation | Average Case (Balanced Tree) | Worst Case (Skewed Tree) | Reason for Worst Case |
|---|---|---|---|
| Search | O(log n) | O(n) | Tree degenerates into a singly linked list if elements are inserted sorted |
| Insert | O(log n) | O(n) | Must traverse the entire height h of the tree |
| Delete | O(log n) | O(n) | Node deletion with 2 children requires finding inorder successor |
| Inorder Traversal | O(n) | O(n) | Every node in the tree is visited exactly once |
Search
- Average Case (Balanced Tree)
- O(log n)
- Worst Case (Skewed Tree)
- O(n)
- Reason for Worst Case
- Tree degenerates into a singly linked list if elements are inserted sorted
Insert
- Average Case (Balanced Tree)
- O(log n)
- Worst Case (Skewed Tree)
- O(n)
- Reason for Worst Case
- Must traverse the entire height h of the tree
Delete
- Average Case (Balanced Tree)
- O(log n)
- Worst Case (Skewed Tree)
- O(n)
- Reason for Worst Case
- Node deletion with 2 children requires finding inorder successor
Inorder Traversal
- Average Case (Balanced Tree)
- O(n)
- Worst Case (Skewed Tree)
- O(n)
- Reason for Worst Case
- Every node in the tree is visited exactly once
Remember
- In a Binary Search Tree (BST), left subtree keys < root < right subtree keys.
- Inorder traversal (Left, Root, Right) of a BST outputs all keys in sorted ascending order.
- Search, insert, and delete in a BST take O(h) time, which is O(log n) when balanced and O(n) when skewed.
- Self-balancing trees (AVL and Red-Black) guarantee O(log n) search by performing rotations when subtrees become uneven.
Check yourself
Question 1
What is the maximum number of nodes in a binary tree of height h (where height of root node alone is 0)?Question 2
If the postorder traversal of a binary search tree is , what is the root node?