'My implementation of Breadth First Search with forEach doesn't work

Here is my code inside a BinarySearchTree class. I don't know if it is because of the behaviour of forEach, or because somewhere in my code is wrong.

class BinarySearchTree {
    constructor() {
        this.root = null;

    }
    insert(val) {
        let newNode = new Node(val)
        if (!this.root) {
            this.root = newNode;
            return this;
        } else {
            let level = this.root
            //             if (val < level.value && level.left){
            //                 level = level.left
            while (true) {
                if (val < level.value) {
                    if (level.left) {
                        level = level.left
                    } else if (!level.left) {
                        level.left = newNode;
                        return this
                    }
                }
                else if (val > level.value) {
                    if (level.right) {
                        level = level.right
                    } else if (!level.right) {
                        level.right = newNode;
                        return this
                    }
                }
            }
        }
    }
    BFS() {
        let data = [];
        let queue = [];
        if (!this.root) {
            return false
        } else if (this.root) {
            queue.push(this.root)
            while (queue.length) {
                queue.forEach(function (element) {
                    if (element.left) {
                        queue.push(element.left)
                    }
                    if (element.right) {
                        queue.push(element.right)
                    }
                    queue.shift()
                    data.push(element)
                })
            }
            return data
        }
    }

}

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

Here is the input

tree.insert(50)
tree.insert(70)
tree.insert(43)
tree.insert(45)
tree.insert(18)
tree.insert(52)
tree.insert(59)
console.log(tree.BFS())

Here is the output

[
  Node {
    value: 50,
    left: Node { value: 43, left: [Node], right: [Node] },
    right: Node { value: 70, left: [Node], right: null }
  },
  Node {
    value: 43,
    left: Node { value: 18, left: null, right: null },
    right: Node { value: 45, left: null, right: null }
  },
  Node { value: 18, left: null, right: null },
  Node { value: 18, left: null, right: null },
  Node { value: 45, left: null, right: null }
]

As you can see, there are duplications and also some nodes of the tree aren't showed at all. Thank everyone in advance!

javascriptalgorithmbreadth-first-search


Solution 1:[1]

If you call forEach, you should not modify the underlying array. All kinds of hard-to-understand behavior will result.

Solution 2:[2]

As mentioned by @JDB, you should not modify the underlying array in forEach.

Although you don't need to use forEach for BFS in this case as you are only traversing the tree. You can process one element at a time from the front of the queue until the queue is empty.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(val) {
    let newNode = new Node(val)
    if (!this.root) {
      this.root = newNode;
      return this;
    } else {
      let level = this.root
      //             if (val < level.value && level.left){
      //                 level = level.left
      while (true) {
        if (val < level.value) {
          if (level.left) {
            level = level.left
          } else if (!level.left) {
            level.left = newNode;
            return this
          }
        } else if (val > level.value) {
          if (level.right) {
            level = level.right
          } else if (!level.right) {
            level.right = newNode;
            return this
          }
        }
      }
    }
  }

  BFS() {
    let data = [];
    let queue = [];
    if (!this.root) {
      return false
    } else if (this.root) {
      queue.push(this.root)
      while (queue.length) {
        const element = queue[0]
        data.push(element)
        if (element.left) {
          queue.push(element.left)
        }
        if (element.right) {
          queue.push(element.right)
        }
        queue.shift()
      }
      return data
    }
  }
}

const tree = new BinarySearchTree();
tree.insert(50)
tree.insert(70)
tree.insert(43)
tree.insert(45)
tree.insert(18)
tree.insert(52)
tree.insert(59)
const result = tree.BFS()
for (r of result) console.log(r)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 JDB
Solution 2 PR7

Related Questions