DSA Trees

What Is Tree?

A tree structure arranges information in a layered hierarchy, where each element expands into sub-elements through directional links, forming a branching system. Unlike arrays or linked lists, which are linear, trees grow outward like an actual tree, making them great for representing hierarchies.

In a tree, each element is known as a node; the highest node is the root, and nodes that link downward create branches, while those without further links are referred to as leaf nodes.

Key Terms

• Root Node: The topmost node that initiates the entire tree structure.
• Child Node: A node directly connected beneath another node.
• Parent Node: A node that has one or more downward connections to other nodes.
• Leaf Node: A node that has no children and ends a path.
• Subtree: Any smaller tree formed under a node within the larger tree.
• Edge: A connection that links one node to another.
• Depth: Counts how many levels down a node is from the root.
• Height: Measures the longest downward path from a node to a leaf.

Why Trees Are Important

• They structure data in a way that allows fast searching, insertion, and deletion.
• Trees are used in file systems, decision-making, AI, compilers, and databases.
• They can represent data with multiple branches, unlike linear structures.

Common Types of Trees

• Binary Tree: A tree where no node has more than two direct descendants.
• Binary Search Tree (BST): A binary tree organized so that left nodes hold lesser values and right nodes hold greater ones.
• Balanced Tree: A tree where nodes are kept evenly distributed to avoid skewed shapes.
• AVL Tree: A self-balancing BST where the height difference of left and right subtrees is always within 1.
• B-Trees: A multi-level tree optimized for reading and writing large blocks of sorted data, commonly used in storage systems.
• N-ary Tree: A flexible tree structure where any node can branch into multiple child nodes beyond just two.
• Trie: A tree used for storing words, where each level represents a character.

Real-World Analogy

Think of a tree as a company hierarchy:

• The CEO is the root.
• Each manager reports to a higher-level boss — that’s the parent-child relationship.
• Employees without subordinates are like leaf nodes.
• Departments under managers are like subtrees.

Operations on Trees

Tree Traversal Methods

• Inorder (Left → Root → Right): Useful for BSTs to get sorted output.
• Preorder (Root → Left → Right): Used when saving or cloning the tree.
• Postorder (Left → Right → Root): Useful when dismantling a tree by clearing child nodes before touching their parent.
• Level Order (Breadth-First): Traverse layer by layer using a queue.

Example

    10       
    /  \     
  5   15    
 / \      \    
3   7    20

• Root: 10
• Left Subtree: Starts from 5
• Right Subtree: Starts from 15
• Leaves: 3, 7, 20
• Inorder Traversal: 3 → 5 → 7 → 10 → 15 → 20

Use Cases of Trees

• Search systems use trie structures to efficiently map and fetch word predictions based on user input prefixes.
• Operating Systems use trees to manage files and directories.
• Routing Algorithms use trees to map optimal paths.
• Games & AI use decision trees for strategy and prediction.