# [DSA] Trees Traversal

---

# Giới thiệu

Trees Traversal (duyệt cây) là cách để lấy tất cả các node của cây. Không như các kiểu dữ liệu linear như linked list, array, queue, stack chỉ lấy dữ liệu theo một chiều, trees có thể lấy tất cả các node theo nhiều cách khác nhau.

Có 2 cách duyệt cây:

* Depth First traversal (DFS)
    
    * Preorder traversal
        
    * Inorder traversal
        
    * Postorder traversal
        
* Breadth First traversal (BFS)
    

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1742312923957/fcd64862-68b1-47f5-8d2c-3947069e5f86.png align="center")

Tiếp tục các đoạn code trong phần [**\[DSA\] Binary Search Trees**](https://triluong.hashnode.dev/dsa-binary-search-trees) ta tiến hành các cách duyệt cây nhị phân (Trees traversal)

# Bread first traversal (BFS)

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1742312963365/7fd3d53c-f1d6-4d15-b901-8c2c16d76031.png align="center")

```jsx
  BFS() {
    let data = [];
    let queue = [];
    let node = this.root;

    queue.push(node);

    while (queue.length) {
      node = queue.shift();
      data.push(node.value);
      if (node.left) {
        queue.push(node.left);
      }

      if (node.right) {
        queue.push(node.right);
      }
    }

    return data;
  }
```

# Depth first traversal

## Preorder

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1742312977219/d312a9ef-b415-43b6-b7ad-164043791784.png align="center")

```jsx
  DFSPreOrder() {
    var data = [];
    function traversal(node) {
      data.push(node.value);
      if (node.left) {
        traversal(node.left);
      }
      if (node.right) {
        traversal(node.right);
      }
    }

    traversal(this.root);
    return data;
  }
```

## Postorder

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1742313121115/b7bf4588-d238-4af5-bd0b-12e595d765c8.png align="center")

```jsx
  DFSPostOrder() {
    var data = [];
    function traversal(node) {
      if (node.left) {
        traversal(node.left);
      }
      if (node.right) {
        traversal(node.right);
      }
      data.push(node.value);
    }
    traversal(this.root);
    return data;
  }
```

## Inorder

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1742313130279/6eb841cc-0c13-4d70-8dd6-6a56f2ce2cd6.png align="center")

```jsx
  DFSInOrder() {
    var data = [];
    function traversal(node) {
      if (node.left) {
        traversal(node.left);
      }
      data.push(node.value);
      if (node.right) {
        traversal(node.right);
      }
    }
    traversal(this.root);
    return data;
  }
```