A tree is a hierarchical data structure with nodes connected by edges, widely used in searching, sorting, and organizing data efficiently. Key terms include:
- Root: The top node.
- Parent/Child: Connections between nodes.
- Leaf: A node with no children.
- Height: Longest path from root to a leaf.
Types of Trees:
- Binary Tree: Each node has at most two children.
- Binary Search Tree (BST): Left child < parent < right child.
- Balanced Tree: Height difference between subtrees is minimal.
- Complete Tree: All levels are filled except the last.
Common Operations:
- Traversal: Inorder, Preorder, Postorder, Level-order.
- Insert: Add nodes.
- Search/Delete: Locate or remove nodes.
Applications:
- Binary Search Tree: Efficient search.
- Heap: Priority queues.
- Trie: Fast string searches.
- Segment Tree: Range queries.
Trees are crucial in databases, file systems, and algorithms.
