binaryTree levelOrder

hojas · hojas · commit 56ab713ff8ae · 2024-07-21T11:14:49.000+08:00
diff --git a/src/1-data-structures/4-tree/binary-tree/BinaryTreeNode.test.ts b/src/1-data-structures/4-tree/binary-tree/BinaryTreeNode.test.ts
@@ -1,5 +1,11 @@
 import { describe, expect, it } from 'vitest'
-import { BinaryTreeNode, inorderTraversal, postorderTraversal, preorderTraversal } from './BinaryTreeNode'
+import {
+  BinaryTreeNode,
+  inorderTraversal,
+  levelOrder,
+  postorderTraversal,
+  preorderTraversal,
+} from './BinaryTreeNode'
 
 function createBinaryTree() {
   const root = new BinaryTreeNode(1)
@@ -20,6 +26,12 @@ describe('binaryTreeNode', () => {
     expect(node.right).toBeNull()
   })
 
+  it('should level order traversal', () => {
+    const root = createBinaryTree()
+    const res = levelOrder(root)
+    expect(res).toEqual([[1], [2, 3], [4, 5, 6, 7]])
+  })
+
   it('should preorderTraversal', () => {
     const root = createBinaryTree()
     const res = preorderTraversal(root)
diff --git a/src/1-data-structures/4-tree/binary-tree/BinaryTreeNode.ts b/src/1-data-structures/4-tree/binary-tree/BinaryTreeNode.ts
@@ -22,21 +22,20 @@ export function levelOrder(root: BinaryTreeNode | null): number[][] {
   const res: number[][] = []
   const q = [root]
 
-  while (q.length) {
+  while (q.length !== 0) {
     const len = q.length
-    const level = []
+    const arr: number[] = []
 
     for (let i = 0; i < len; i++) {
       const node = q.shift() as BinaryTreeNode
-      level.push(node.value)
-
-      if (node.left) {
+      arr.push(node.value)
+      if (node.left)
         q.push(node.left)
-      }
-      if (node.right) {
+      if (node.right)
         q.push(node.right)
-      }
     }
+
+    res.push(arr)
   }
 
   return res
