Tree Data Structure | Binary Tree· BST

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

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Complete guide to tree data structures for coding interviews. Master binary trees, BST, and tree traversal with principl… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• 그래프 자료구조 | 인접 리스트, 인접 행렬, 탐색 완벽 정리
• BFS와 DFS | 그래프 탐색 알고리즘 완벽 정리
• [Hash Table | O(1) Search Data Structure Complete Guide](/en/blog/algorithm-series-03-hash-table/

---

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, Data Structure, Tree, BST, Binary Tree, Coding Interview 등으로 검색하시면 이 글이 도움이 됩니다.