트리 기본: 구조, 용어, 및 사용 사례

Source: Dev.to

What Is a Tree?

A Tree is a hierarchical, non‑linear data structure made of nodes.

Each node:

• Stores a value
• Has zero or more children
• Has exactly one parent (except the root)

Common real‑world analogies:

• Folder structures
• Company org charts
• Website DOM

Trees are ideal when the data naturally forms a hierarchy.

Common Types of Trees

There are many variations of trees, but these are the ones most used in software and interviews:

• Binary Tree
• Binary Search Tree (BST)
• AVL Tree
• Red‑Black Tree
• N‑ary Tree
• Trie (Prefix Tree)

This post focuses on the Binary Tree, since most traversal logic starts here.

What Is a Binary Tree?

A Binary Tree is a tree where each node has at most two children.

class Node {
  constructor(key, left = null, right = null) {
    this.left = left;
    this.right = right;
    this.val = key;
  }
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);

// The tree structure:
//        1
//       / \
//      2   3
//     / \
//    4   5

You can also build the tree with nested constructor calls, but this form is more readable for beginners.

Tree Traversals

Traversals describe how we “walk” through a tree. There are four fundamental traversal patterns:

• Inorder
• Preorder
• Postorder
• Breadth‑First Search (Level Order)

We’ll go deeper into each in Part 1.2, but here is a quick preview.

Inorder (Left → Root → Right)

Useful in Binary Search Trees because it returns nodes in sorted order.

function inorderTraversal(node) {
  if (node !== null) {
    inorderTraversal(node.left);
    console.log(node.val);
    inorderTraversal(node.right);
  }
}

Preorder (Root → Left → Right)

Good for serializing or copying trees.

function preorderTraversal(node) {
  if (node !== null) {
    console.log(node.val);
    preorderTraversal(node.left);
    preorderTraversal(node.right);
  }
}

Postorder (Left → Right → Root)

Commonly used when deleting or evaluating trees.

function postorderTraversal(node) {
  if (node !== null) {
    postorderTraversal(node.left);
    postorderTraversal(node.right);
    console.log(node.val);
  }
}

Breadth‑First Search (Level Order)

Visits each level of the tree from left to right.

function breadthFirstTraversal(root) {
  const queue = [root];

  while (queue.length > 0) {
    const currentNode = queue.shift();
    console.log(currentNode.val);

    if (currentNode.left) queue.push(currentNode.left);
    if (currentNode.right) queue.push(currentNode.right);
  }
}

Why Traversals Matter

Different problems require different traversal strategies:

• Inorder → sorted output in BSTs
• Preorder → reconstructing or serializing trees
• Postorder → evaluating expressions, deleting structures
• BFS → shortest path, level‑by‑level processing

You’ll see these patterns repeatedly in interviews.

Continue the Data Structures Series

This post is part of an ongoing Data Structures Series focused on clarity, real‑world intuition, and JavaScript implementations.

👉 Data Structures Series — Overview