Tree Data Structure | Binary Tree, BST, Traversal Complete Guide

Introduction

”Perfect Representation of Hierarchical Structure”

Trees are data structures that represent hierarchical relationships. File systems, DOM, organizational charts are all trees.

---

1. Tree Basics

Terminology

        1  ← Root
       / \
      2   3  ← Children
     / \
    4   5  ← Leaves

- Node: 1, 2, 3, 4, 5
- Edge: Lines connecting nodes
- Parent: Parent of 2 is 1
- Child: Children of 1 are 2, 3
- Sibling: 2 and 3
- Depth: Distance from root (depth of 4 = 2)
- Height: Max distance to leaf (tree height = 2)
- Level: Nodes at same depth

Python Implementation

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

# Create tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

---

2. Tree Traversal

Preorder Traversal

Parent → Left → Right:

def preorder(node):
    if not node:
        return []
    
    return [node.val] + preorder(node.left) + preorder(node.right)

# Tree:
#        1
#       / \
#      2   3
#     / \
#    4   5
#
# Result: [1, 2, 4, 5, 3]

Iterative Implementation (using stack):

def preorder_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.val)
        
        # Push right first (pops later)
        if node.right:
            stack.append(node.right)
        # Push left later (pops first)
        if node.left:
            stack.append(node.left)
    
    return result

Inorder Traversal

Left → Parent → Right:

def inorder(node):
    if not node:
        return []
    
    return inorder(node.left) + [node.val] + inorder(node.right)

# Result: [4, 2, 5, 1, 3]
# In BST: sorted order!

Postorder Traversal

Left → Right → Parent:

def postorder(node):
    if not node:
        return []
    
    return postorder(node.left) + postorder(node.right) + [node.val]

# Result: [4, 5, 2, 3, 1]

Level Order Traversal

Using BFS:

from collections import deque

def level_order(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.val)
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

# Result: [1, 2, 3, 4, 5]

---

3. Binary Search Tree (BST)

BST Rules

Left < Parent < Right:

        5
       / \
      3   7
     / \ / \
    2  4 6  8

Inorder: [2, 3, 4, 5, 6, 7, 8] (sorted!)

BST Insertion

def insert_bst(root, val):
    if not root:
        return TreeNode(val)
    
    if val < root.val:
        root.left = insert_bst(root.left, val)
    else:
        root.right = insert_bst(root.right, val)
    
    return root

# Usage
root = TreeNode(5)
root = insert_bst(root, 3)
root = insert_bst(root, 7)
root = insert_bst(root, 2)

# Result:
#        5
#       / \
#      3   7
#     /
#    2

Iterative Implementation:

def insert_bst_iterative(root, val):
    if not root:
        return TreeNode(val)
    
    current = root
    while True:
        if val < current.val:
            if current.left is None:
                current.left = TreeNode(val)
                break
            current = current.left
        else:
            if current.right is None:
                current.right = TreeNode(val)
                break
            current = current.right
    
    return root

BST Search

def search_bst(root, val):
    if not root:
        return None
    
    if root.val == val:
        return root
    
    if val < root.val:
        return search_bst(root.left, val)
    else:
        return search_bst(root.right, val)

# Time Complexity:
# - Average: O(log n) - balanced tree
# - Worst: O(n) - skewed tree (1→2→3→4→5)

Iterative Implementation:

def search_bst_iterative(root, val):
    current = root
    
    while current:
        if current.val == val:
            return current
        elif val < current.val:
            current = current.left
        else:
            current = current.right
    
    return None

BST Advantages:

# Maintain sorted data
def get_sorted(root):
    return inorder(root)  # O(n)

# Find min/max
def find_min(root):
    while root.left:
        root = root.left
    return root.val

def find_max(root):
    while root.right:
        root = root.right
    return root.val

---

4. Problem Solving

Problem 1: Maximum Depth

def max_depth(root):
    """
    Find maximum depth of tree
    """
    if not root:
        return 0
    
    left_depth = max_depth(root.left)
    right_depth = max_depth(root.right)
    
    return max(left_depth, right_depth) + 1

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth(root))  # 3

Problem 2: Symmetric Tree

def is_symmetric(root):
    """
    Check if tree is symmetric
    """
    def is_mirror(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        
        return (left.val == right.val and
                is_mirror(left.left, right.right) and
                is_mirror(left.right, right.left))
    
    return is_mirror(root.left, root.right) if root else True

# Test
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.right.right = TreeNode(3)
print(is_symmetric(root))  # True

Problem 3: Lowest Common Ancestor (LCA)

def lowest_common_ancestor(root, p, q):
    """
    Find lowest common ancestor of two nodes (BST)
    """
    if not root:
        return None
    
    # Both in left subtree
    if p.val < root.val and q.val < root.val:
        return lowest_common_ancestor(root.left, p, q)
    
    # Both in right subtree
    if p.val > root.val and q.val > root.val:
        return lowest_common_ancestor(root.right, p, q)
    
    # Split point = LCA
    return root

Problem 4: Validate BST

def is_valid_bst(root):
    """
    Check if tree is a valid BST
    """
    def validate(node, min_val, max_val):
        if not node:
            return True
        
        if node.val <= min_val or node.val >= max_val:
            return False
        
        return (validate(node.left, min_val, node.val) and
                validate(node.right, node.val, max_val))
    
    return validate(root, float('-inf'), float('inf'))

# Test
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(7)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
print(is_valid_bst(root))  # True

---

5. Practical Tips

Tree Problem Approach

# 1. Think recursively
# Most tree problems solved with recursion

# 2. Clear base case
# if not root: return ...

# 3. Choose traversal method
# Preorder: process parent first
# Inorder: BST sorting
# Postorder: process children first
# Level: shortest path

Common Patterns

Pattern 1: Recursive Template

def tree_function(root):
    # Base case
    if not root:
        return base_value
    
    # Recursive case
    left_result = tree_function(root.left)
    right_result = tree_function(root.right)
    
    # Combine results
    return combine(root.val, left_result, right_result)

Pattern 2: Level Order with Queue

from collections import deque

def level_order_template(root):
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        level_size = len(queue)
        level = []
        
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        
        result.append(level)
    
    return result

---

Summary

Key Points

1. Tree: Hierarchical structure, root-child relationships
2. Traversal: Preorder, Inorder, Postorder, Level
3. BST: Left < Parent < Right, O(log n) search
4. Recursion: Most problems solved recursively

Time Complexity

Operation	Binary Tree	BST (balanced)	BST (skewed)
Search	O(n)	O(log n)	O(n)
Insert	O(n)	O(log n)	O(n)
Delete	O(n)	O(log n)	O(n)
Traversal	O(n)	O(n)	O(n)

When to Use

Situation	Tree Type	Reason
Hierarchical data	General Tree	Natural representation
Fast search	BST	O(log n) operations
Sorted data	BST	Inorder gives sorted
Priority queue	Heap	O(log n) insert/delete

---

Recommended Problems

Beginner

• LeetCode 104: Maximum Depth of Binary Tree
• LeetCode 101: Symmetric Tree
• LeetCode 226: Invert Binary Tree

Intermediate

• LeetCode 98: Validate Binary Search Tree
• LeetCode 102: Binary Tree Level Order Traversal
• LeetCode 236: Lowest Common Ancestor

Advanced

• LeetCode 297: Serialize and Deserialize Binary Tree
• LeetCode 124: Binary Tree Maximum Path Sum
• LeetCode 145: Binary Tree Postorder Traversal

---

Related Posts

• Arrays and Lists | Essential Data Structures
• Stack and Queue | LIFO and FIFO
• Graph Data Structure | Complete Guide
• BFS and DFS | Graph Traversal

---

Keywords

Tree, Binary Tree, BST, Binary Search Tree, Tree Traversal, Preorder, Inorder, Postorder, Level Order, Recursion, Data Structure, Coding Interview, Algorithm