코딩테스트 트리

// Node 클래스 정의
class TreeNode {
  constructor(value) {
    this.value = value
    this.left = null
    this.right = null
  }
}

// 이진 트리 클래스 정의
class BinaryTree {
  constructor() {
    this.root = null
  }

  // 노드 추가 함수
  insert(value) {
    const newNode = new TreeNode(value)
    if (this.root === null) {
      this.root = newNode
      return
    }

    const queue = [this.root]
    while (queue.length > 0) {
      const current = queue.shift()
      if (!current.left) {
        current.left = newNode
        return
      } else if (!current.right) {
        current.right = newNode
        return
      } else {
        queue.push(current.left)
        queue.push(current.right)
      }
    }
  }

  // 전위 순회
  preOrderTraversal(node, result = []) {
    if (node) {
      result.push(node.value)
      this.preOrderTraversal(node.left, result)
      this.preOrderTraversal(node.right, result)
    }
    return result
  }

  // 중위 순회
  inOrderTraversal(node, result = []) {
    if (node) {
      this.inOrderTraversal(node.left, result)
      result.push(node.value)
      this.inOrderTraversal(node.right, result)
    }
    return result
  }

  // 후위 순회
  postOrderTraversal(node, result = []) {
    if (node) {
      this.postOrderTraversal(node.left, result)
      this.postOrderTraversal(node.right, result)
      result.push(node.value)
    }
    return result
  }
}

// 트리 생성 및 순회 테스트
const tree = new BinaryTree()
tree.insert(1)
tree.insert(2)
tree.insert(3)
tree.insert(4)
tree.insert(5)
tree.insert(6)
tree.insert(7)

console.log('전위 순회:', tree.preOrderTraversal(tree.root)) // [1, 2, 4, 5, 3, 6, 7]
console.log('중위 순회:', tree.inOrderTraversal(tree.root)) // [4, 2, 5, 1, 6, 3, 7]
console.log('후위 순회:', tree.postOrderTraversal(tree.root)) // [4, 5, 2, 6, 7, 3, 1]