Unit 7: Trees  (DSA)– Exam Revision Notes

1. Introduction to Trees

• Tree = Non-linear data structure consisting of nodes connected by edges.
  
• Root Node – Topmost node.
  
• Child Node – Node directly connected below another node.
  
• Parent Node – Node having child nodes.
  
• Leaf Node – Node with no children.
  
• Level – Distance from root (root = level 0).
  
• Depth/Height – Longest path from node to a leaf.
  

2. Basic Operations in Binary Tree

1. Insertion – Add a new node at correct position.
   
2. Deletion – Remove node and adjust tree to maintain structure.
   
3. Traversal – Visit all nodes systematically.
   
   • Pre-order: Root → Left → Right
     
   • In-order: Left → Root → Right
     
   • Post-order: Left → Right → Root
     

3. Tree Search and Insertion/Deletion

• Search: Locate a specific node using traversal or binary search in BST.
  
• Insertion: Add node maintaining Binary Search Tree (BST) property.
  
• Deletion: Remove node while maintaining BST property:
  
  1. Node with no children → delete directly.
     
  2. Node with one child → replace node with child.
     
  3. Node with two children → replace with inorder predecessor/successor.
     

4. Balanced Trees

• Balanced Tree: Height of left and right subtrees differs ≤ 1.
  
• AVL Tree: Self-balancing binary search tree.
  
  • Rotations:
    
    1. Single rotation (Left/Right)
       
    2. Double rotation (Left-Right, Right-Left)
       
  • Ensures O(log n) height, improving search, insertion, deletion efficiency.
    

5. Special Trees

1. Huffman Tree
   
   • Used in data compression.
     
   • Build tree using frequency of symbols.
     
2. Game Tree
   
   • Represents possible moves in games.
     
   • Nodes = game states; edges = moves.
     
3. B-Tree
   
   • Multi-way search tree for disk-based storage.
     
   • Maintains balance for efficient search, insert, delete.
     

6. Applications of Trees

1. Database Indexing – B-trees for fast retrieval.
   
2. Expression Parsing – Expression trees for arithmetic evaluation.
   
3. Huffman Encoding – Data compression.
   
4. Decision Making – Game trees, AI algorithms.
   
5. Hierarchical Structures – File systems, organizational charts.
   

✅ Key Takeaways – Unit 7

• Trees = non-linear hierarchical structure with nodes and edges.
  
• Traversals: pre-order, in-order, post-order.
  
• Balanced trees (AVL, B-tree) optimize search and update operations.
  
• Huffman and game trees are used in compression and AI applications.
• Trees form foundation for efficient algorithms and hierarchical data representation.