Tree Traversal Algorithms

Traversal is visiting each node exactly once in a systematic way. Trees use Recursion for traversal.

Traversal Methods — Comparison

Worked Example: All Traversals

        50
       /  \
      30    70
     / \   / \
    20  40 60  80

Binary Search Tree (BST) Property

For every node:

• Left subtree contains only values less than the node.
• Right subtree contains only values greater than the node.
• Both subtrees are also BSTs (recursive property).

BST Operations — Time Complexity

BST Search Algorithm

1. If Root is NULL → Not Found.
2. If Key == Root → Found!
3. If Key < Root → Search Left subtree.
4. If Key > Root → Search Right subtree.

This is a divide-and-conquer approach — each comparison eliminates half the tree.

BST Insertion

Find the correct empty position by following BST property:

• Key < Current → Go Left.
• Key > Current → Go Right.
• When you reach NULL → Insert here.

BST Deletion — The 3 Cases

Worked Example — Delete 30 from the BST above (2 children):

1. Node 30 has 2 children (20 and 40).
2. Find Inorder Successor of 30 = smallest in right subtree = 40.
3. Replace 30's value with 40.
4. Delete old 40 node (which is a leaf — Case 1).
5. Result:

        50
       /  \
      40    70
     /    / \
    20   60  80

Inorder Predecessor vs Successor