DS/Trees

Types of Trees:

A. General Trees

• Nodes can have any number of children.

B. Binary Trees

• Each node has at most two children.

  • Full Binary Tree: Every node has either 0 or 2 children.

  • Complete Binary Tree: All levels except possibly the last are completely filled, and nodes are as left as possible.

  • Perfect Binary Tree: All internal nodes have two children, and all leaf nodes are at the same level.

  • Skewed Tree: All nodes have only one child, forming a linear structure (left-skewed or right-skewed).

C. Binary Search Tree (BST)

• A binary tree where the left subtree contains nodes with values less than the root, and the right subtree contains nodes with values greater than the root.

D. Balanced Trees

• Trees like AVL, Red-Black, or B-Trees ensure height balance for efficient operations.

E. Specialized Trees

• N-ary Trees: Nodes can have up to N children.

• Trie (Prefix Tree): Used for efficient information retrieval, like searching in dictionaries.

• Segment Tree: Used for range queries in arrays.

• Fenwick Tree: Efficient for prefix sum and range updates.

• Heap: A specialized tree-based structure satisfying the heap property (Max-Heap or Min-Heap).

Traversals

raversals are ways to visit all nodes in a tree:

A. Depth-First Search (DFS)

1. Inorder Traversal (Left-Root-Right):

   • Visit left subtree, root, then right subtree.

   • Used in BSTs to retrieve sorted data.

2. Preorder Traversal (Root-Left-Right):

   • Visit root, left subtree, then right subtree.

   • Useful for creating a copy of the tree.

3. Postorder Traversal (Left-Right-Root):

   • Visit left subtree, right subtree, then root.

   • Useful for deleting a tree.

B. Breadth-First Search (BFS)

• Level Order Traversal:

  • Visit nodes level by level.