Tree

7 min read

Think of a family tree or an organization chart. A tree is a data structure that looks like an upside-down tree, where:

  • The root is at the top (like a CEO)
  • Branches connect different levels
  • Leaves are at the bottom (employees with no subordinates)
  • Each item is called a node

Real-world analogy: A company hierarchy where each manager can have multiple employees, but each employee has only one direct boss.

Tree Terminology: #

  • Root: The top node (CEO)
  • Parent: A node that has children (Manager)
  • Child: A node that has a parent (Employee)
  • Leaf: A node with no children (Entry-level employee)
  • Height: Levels from root to deepest leaf
  • Depth: Levels from root to a specific node

1. Binary Trees #

What is it? #

A binary tree is like a family tree where each person can have at most 2 children (left child and right child).

Structure: #

       A
      / \
     B   C
    / \   \
   D   E   F

Real-world Example: Decision Tree #

Think of a “20 Questions” game:

  • Each question has only 2 answers: Yes or No
  • Based on your answer, you go left (No) or right (Yes)
  • You continue until you reach the final answer

Example Decision Tree: “Guess the Animal”

           Is it a mammal?
          /              \
       No/                \Yes
        /                  \
   Is it a bird?        Does it live on land?
   /         \           /              \
  No/         \Yes      No/              \Yes
 Fish       Bird       Whale            Dog

Simple Code Example (Python): #

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self, root_data):
        self.root = TreeNode(root_data)
    
    def add_left_child(self, parent_node, data):
        parent_node.left = TreeNode(data)
        return parent_node.left
    
    def add_right_child(self, parent_node, data):
        parent_node.right = TreeNode(data)
        return parent_node.right
    
    def print_tree(self, node, level=0):
        if node:
            self.print_tree(node.right, level + 1)
            print("  " * level + str(node.data))
            self.print_tree(node.left, level + 1)

# Usage - Creating the animal guessing tree
tree = BinaryTree("Is it a mammal?")
root = tree.root

# Left side (No - not a mammal)
bird_question = tree.add_left_child(root, "Is it a bird?")
tree.add_left_child(bird_question, "Fish")
tree.add_right_child(bird_question, "Bird")

# Right side (Yes - is a mammal)
land_question = tree.add_right_child(root, "Does it live on land?")
tree.add_left_child(land_question, "Whale")
tree.add_right_child(land_question, "Dog")

tree.print_tree(tree.root)

Use Cases: #

  • Decision trees in AI
  • File system directories
  • HTML/XML document structure
  • Mathematical expression trees

2. Binary Search Trees (BST) #

What is it? #

A Binary Search Tree is like a sorted binary tree with a special rule:

  • Left child is always smaller than parent
  • Right child is always larger than parent
  • This makes searching super fast (like a phone book)

Structure: #

       50
      /  \
    30    70
   / \   / \
  20 40 60 80

Real-world Example: Company Employee ID System #

Imagine organizing employee IDs for quick lookup:

  • Boss has ID 50
  • Employees with smaller IDs (30, 20, 40) go to the left
  • Employees with larger IDs (70, 60, 80) go to the right

Simple Code Example (Python): #

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self, data):
        if not self.root:
            self.root = BSTNode(data)
        else:
            self._insert_recursive(self.root, data)
    
    def _insert_recursive(self, node, data):
        if data < node.data:
            if node.left is None:
                node.left = BSTNode(data)
            else:
                self._insert_recursive(node.left, data)
        else:
            if node.right is None:
                node.right = BSTNode(data)
            else:
                self._insert_recursive(node.right, data)
    
    def search(self, data):
        return self._search_recursive(self.root, data)
    
    def _search_recursive(self, node, data):
        if not node:
            return False
        
        if data == node.data:
            return True
        elif data < node.data:
            return self._search_recursive(node.left, data)
        else:
            return self._search_recursive(node.right, data)
    
    def print_sorted(self, node):
        # In-order traversal gives sorted output
        if node:
            self.print_sorted(node.left)
            print(node.data, end=" ")
            self.print_sorted(node.right)

# Usage - Employee ID system
company_bst = BinarySearchTree()

# Adding employee IDs
employee_ids = [50, 30, 70, 20, 40, 60, 80]
for emp_id in employee_ids:
    company_bst.insert(emp_id)

print("Employee IDs in sorted order:")
company_bst.print_sorted(company_bst.root)  # Output: 20 30 40 50 60 70 80

print(f"\nIs employee 40 in system? {company_bst.search(40)}")  # True
print(f"Is employee 90 in system? {company_bst.search(90)}")    # False

Advantages of BST: #

  • Fast searching: O(log n) average time
  • Automatic sorting: In-order traversal gives sorted data
  • Efficient insertion/deletion

Disadvantages: #

  • Can become unbalanced (like a linked list)
  • Worst case: O(n) time complexity

3. Tree Traversals #

Tree traversal is like visiting every room in a house. There are different ways to do it:

1. In-Order Traversal (Left → Root → Right) #

Like reading a book: Left page, then middle, then right page

Process: Left subtree → Current node → Right subtree

Real-world analogy: Organizing books on a shelf from left to right

2. Pre-Order Traversal (Root → Left → Right) #

Like making a backup: Save the folder first, then its contents

Process: Current node → Left subtree → Right subtree

Real-world analogy: Company announcement flows from CEO down to employees

3. Post-Order Traversal (Left → Right → Root) #

Like calculating folder sizes: Calculate subfolder sizes first, then main folder

Process: Left subtree → Right subtree → Current node

Real-world analogy: Calculating total expenses (departments first, then company total)

Code Example for All Traversals: #

class TreeTraversal:
    def __init__(self, root):
        self.root = root
    
    def inorder(self, node, result=[]):
        """Left → Root → Right (gives sorted output for BST)"""
        if node:
            self.inorder(node.left, result)
            result.append(node.data)
            self.inorder(node.right, result)
        return result
    
    def preorder(self, node, result=[]):
        """Root → Left → Right (good for copying tree)"""
        if node:
            result.append(node.data)
            self.preorder(node.left, result)
            self.preorder(node.right, result)
        return result
    
    def postorder(self, node, result=[]):
        """Left → Right → Root (good for deleting tree)"""
        if node:
            self.postorder(node.left, result)
            self.postorder(node.right, result)
            result.append(node.data)
        return result

# Example with our BST
traversal = TreeTraversal(company_bst.root)

print("In-order (sorted):", traversal.inorder(company_bst.root, []))
# Output: [20, 30, 40, 50, 60, 70, 80]

print("Pre-order (root first):", traversal.preorder(company_bst.root, []))
# Output: [50, 30, 20, 40, 70, 60, 80]

print("Post-order (root last):", traversal.postorder(company_bst.root, []))
# Output: [20, 40, 30, 60, 80, 70, 50]

When to Use Each Traversal: #

In-Order:

  • Getting sorted data from BST
  • Mathematical expression evaluation

Pre-Order:

  • Copying/cloning a tree
  • Prefix expression evaluation
  • File system backup

Post-Order:

  • Deleting a tree safely
  • Calculating directory sizes
  • Postfix expression evaluation

4. Balanced Trees Overview #

The Problem with Regular BST #

Imagine adding numbers in order: 1, 2, 3, 4, 5

1
 \
  2
   \
    3
     \
      4
       \
        5

This becomes like a linked list – very slow!

What are Balanced Trees? #

Balanced trees automatically reorganize themselves to stay “balanced” (short and wide, not tall and skinny).

AVL Trees #

What is it?: Named after its inventors (Adelson-Velsky and Landis)

  • Self-balancing BST
  • Height difference between left and right subtrees is at most 1
  • Automatic rotations keep it balanced

Real-world analogy: Like a mobile (hanging decoration) that stays balanced

# Simplified AVL concept (not full implementation)
class AVLNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 1  # Height of this node

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

# If balance factor is > 1 or < -1, we need to rotate
def is_balanced(node):
    balance = get_balance(node)
    return -1 <= balance <= 1

When to use AVL:

  • When you need guaranteed fast searches
  • Database indexing
  • When insertions/deletions are less frequent than searches

Red-Black Trees #

What is it?: Another self-balancing BST with these rules:

  • Every node is either red or black
  • Root is always black
  • Red nodes can’t have red children
  • All paths from root to leaves have same number of black nodes

Real-world analogy: Like traffic lights with rules to prevent traffic jams

# Simplified Red-Black concept
class RBNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.color = "RED"  # New nodes are red
        self.parent = None

# Red-Black rules ensure the tree stays balanced
# Complex rotations and recoloring maintain these rules

When to use Red-Black:

  • When you need good performance for all operations
  • Java’s TreeMap and TreeSet
  • Linux kernel’s scheduler
  • More insertions/deletions than AVL can handle efficiently

Comparison: #

FeatureRegular BSTAVL TreeRed-Black Tree
Search TimeO(n) worstO(log n)O(log n)
Insert TimeO(n) worstO(log n)O(log n)
BalanceNoStrictLoose
RotationsNoneMoreFewer
MemoryLessMoreMore

Real-World Applications #

1. File Systems #

C:\
├── Users\
│   ├── Alice\
│   └── Bob\
├── Program Files\
│   ├── Microsoft\
│   └── Adobe\
└── Windows\

Type: General tree (not binary)

2. Database Indexing #

  • B-trees and B+ trees (variations of balanced trees)
  • Used in MySQL, PostgreSQL, MongoDB
  • Enable fast data retrieval

3. Decision Making Systems #

  • Decision trees in machine learning
  • Medical diagnosis systems
  • Loan approval systems

4. Game Development #

  • Game trees for AI (chess, checkers)
  • Scene graphs for 3D graphics
  • Collision detection systems

5. Compilers #

  • Abstract Syntax Trees (AST)
  • Parse trees for code analysis
  • Expression evaluation

6. Network Routing #

  • Spanning trees in network protocols
  • Shortest path algorithms
  • Network topology management

7. Autocomplete/Search #

  • Trie trees for word suggestions
  • Search engines
  • Spell checkers

When to Use Which Tree #

Use Binary Tree When: #

  • Simple hierarchical data
  • Decision-making processes
  • Expression parsing

Use BST When: #

  • Need sorted data
  • Frequent searching
  • Data doesn’t come in sorted order

Use AVL Tree When: #

  • Need guaranteed fast searches
  • More searches than insertions
  • Database applications

Use Red-Black Tree When: #

  • Balanced performance for all operations
  • Frequent insertions and deletions
  • General-purpose applications

Summary #

Trees are like organizational charts in the digital world:

  • Binary Trees: Each node has at most 2 children (like a simple family tree)
  • BST: Organized binary tree for fast searching (like a sorted phone book)
  • Traversals: Different ways to visit all nodes (like different routes through a building)
  • Balanced Trees: Self-organizing trees that stay efficient (like a well-managed organization)

Choose the right tree based on what you need to do most often: searching, inserting, or maintaining balance!

Updated on June 9, 2025