[2026] 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

아래 코드는 text를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

        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

아래 코드는 python를 사용한 구현 예제입니다. 클래스를 정의하여 데이터와 기능을 캡슐화하며. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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): 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 text를 사용한 구현 예제입니다. 코드를 직접 실행해보면서 동작을 확인해보세요.

        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: 다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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: 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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)

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

다음은 python를 활용한 상세한 구현 코드입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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

아래 코드는 python를 사용한 구현 예제입니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

# 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 아래 코드는 python를 사용한 구현 예제입니다. 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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 다음은 python를 활용한 상세한 구현 코드입니다. 필요한 모듈을 import하고, 함수를 통해 로직을 구현합니다. 각 부분의 역할을 이해하면서 코드를 살펴보시기 바랍니다.

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