Trees & BST
What Is a Tree? A Tree is a hierarchical data structure made up of nodes . Each node stores data and links (called edges ) to its child nodes. A / \ B C / \ D E Root: The topmost node (A) Parent/Child: Relationship between connected nodes (A → B, A → C) Leaf: Node with no children (D, E, C) Edge: Connection between two nodes Height: Longest path from root to any leaf Unlike arrays or linked lists, which are linear , trees are non-linear , allowing efficient hierarchical storage. Types of Trees There are many types of trees, but in DSA we mostly work with: Binary Tree – Each node has at most two children (left and right). Binary Search Tree (BST) – A special binary tree that maintains sorted order . AVL Tree , Red-Black Tree – Self-balancing versions of BST. N-ary Tree , Trie , Segment Tree , etc. – Used in more com...