What is a Binary Tree?
A binary tree is a hierarchical data structure in which:
● Each node has at most two children.
● These children are called:
○ Left child
○ Right child
Types of Binary Trees
● Full Binary Tree: Every node has either 0 or 2 children.
● Complete Binary Tree: All levels are fully filled except possibly the last, which is
filled from left to right.
● Perfect Binary Tree: All internal nodes have 2 children and all leaves are at the
same level.
● Balanced Binary Tree: Height difference between left and right subtrees of every
node is minimal.
Time Complexity of Operations in a Binary Tree
Operation Average Worst
Case Case
Insert O(n) O(n)
Delete O(n) O(n)
Search O(n) O(n)
Traversal O(n) O(n)
Example Tree:
mathematica
CopyEdit
A
/ \
B C
/ \
D E
● Height of D = 0 (leaf node)
● Height of E = 0 (leaf node)
● Height of B = 1 + max(Height of D, Height of E) = 1 + max(0, 0) = 1
● Height of C = 0 (leaf node)
● Height of A = 1 + max(Height of B, Height of C) = 1 + max(1, 0) = 2
1. Inorder Traversal (Left, Root, Right)
● Visit the left subtree first.
● Then visit the root node.
● Then visit the right subtree.
● Result: Nodes visited in ascending order in a Binary Search Tree.
Example order: D → B → E → A → C
2. Preorder Traversal (Root, Left, Right)
● Visit the root node first.
● Then the left subtree.
● Then the right subtree.
Example order: A → B → D → E → C
3. Postorder Traversal (Left, Right, Root)
● Visit the left subtree first.
● Then the right subtree.
● Finally the root node.
Example order: D → E → B → C → A
4. Level Order Traversal (Breadth-First)
● Visit nodes level by level from top to bottom, left to right.
● Usually done with a queue.
Example order: A → B → C → D → E
Example Tree:
mathematica
CopyEdit
A
/ \
B C
/ \
D E
What is a Binary Search Tree (BST)?
A Binary Search Tree is a special kind of binary tree with the following properties:
1. Each node has at most two children (left and right).
2. The left subtree of a node contains only nodes with values less than the node's
value.
3. The right subtree of a node contains only nodes with values greater than the
node's value.
4. Both left and right subtrees are also binary search trees.
Why use a BST?
● Allows efficient searching, insertion, and deletion.
● Average time complexity for these operations is O(log n) if the tree is balanced.
● Maintains sorted data and enables quick lookup.
Example BST:
markdown
CopyEdit
15
/ \
10 20
/ \ \
8 12 25
What is an AVL Tree?
An AVL Tree is a self-balancing binary search tree named after its inventors
(Adelson-Velsky and Landis).
Key Features:
● It is a Binary Search Tree (BST), so it maintains the BST property:
○ Left child < Parent node < Right child.
● It automatically keeps itself balanced after insertions and deletions.
● Balance factor of every node is either -1, 0, or +1.
○ Balance Factor = Height of Left Subtree - Height of Right Subtree
● If the balance factor becomes less than -1 or greater than +1, the tree performs
rotations to restore balance.
Why AVL Trees?
● In regular BSTs, the tree can become skewed (like a linked list), causing operations
to degrade to O(n).
● AVL Trees keep the height logarithmic (O(log n)), ensuring efficient operations.
● Maintains fast search, insert, and delete times.
Rotations to Balance AVL Tree
When the tree becomes unbalanced, it uses these rotations:
● Right Rotation (LL Rotation)
● Left Rotation (RR Rotation)
● Left-Right Rotation (LR Rotation)
● Right-Left Rotation (RL Rotation)
Example
Suppose you insert nodes in ascending order: 10, 20, 30
● This will cause a right-heavy tree and imbalance.
● AVL will do a left rotation to balance the tree.
Summary
Operation Time Complexity
Search O(log n)
Insert O(log n)
Delete O(log n)
