Binary Search Tree插入函数异常：未调用即执行且prettyPrint报错

在The Odin Project学习二叉搜索树（BST）时遇到两个异常：

1. insert函数未被主动调用，BST中却自动出现了额外节点
2. TOP提供的prettyPrint函数抛出Cannot read properties of undefined错误
   移除insert函数后一切恢复正常，怀疑树的遍历或函数逻辑存在问题，相关代码如下：

const createNode = (data, left = null, right = null) => {
  return {
    data: data,
    left: left,
    right: right,
  };
};

const tree = (arr) => {
  const sortedArr = mergeSort(removeDuplicates(arr));
  root = buildTree(sortedArr);
  
  // Problem starts here
  const insert = (val, root = this.root) => {
    // base case: if null leaf is reached, insert new node with val.
    if (root === null) {
      const newNode = createNode(val);
      return newNode;
    }

    // traverses down the tree branch until it reaches a null leaf.
    if (val < root.data) {
      root.left = insert(val, root.left);
    } else {
      root.right = insert(val, root.right);
    }
    return root;
    // End of problem
  };
  return { root, insert };
};


const buildTree = (sortedArr, start = 0, end = sortedArr.length - 1) => {
  if (start > end) return null;

  let mid = Math.floor((start + end) / 2);

  let root = sortedArr[mid];
  let node = createNode(root);

  node.left = buildTree(sortedArr, start, mid - 1);
  node.right = buildTree(sortedArr, mid + 1, end);
  return node;
};

const removeDuplicates = (arr) => {
  const arrNoDups = [];
  Array.from(arr).forEach((i) => {
    if (!arrNoDups.includes(i)) {
      arrNoDups.push(i);
    }
  });
  return arrNoDups;
};

// merge sort function
const mergeSort = (arr) => {
  if (arr.length < 2) return arr;

  const mid = Math.floor(arr.length / 2);
  const leftArr = arr.slice(0, mid);
  const rightArr = arr.slice(mid);
  return merge(mergeSort(leftArr), mergeSort(rightArr));
};

const merge = (leftArr, rightArr) => {
  const sortedArr = [];
  let countL = 0;
  let countR = 0;
  while (countL < leftArr.length && countR < rightArr.length) {
    if (leftArr[countL] < rightArr[countR]) {
      sortedArr.push(leftArr[countL]);
      countL++;
    } else {
      sortedArr.push(rightArr[countR]);
      countR++;
    }
  }

  while (countL < leftArr.length) {
    sortedArr.push(leftArr[countL]);
    countL++;
  }

  while (countR < rightArr.length) {
    sortedArr.push(rightArr[countR]);
    countR++;
  }
  return sortedArr;
};

// Console log tree visual
const prettyPrint = (node, prefix = '', isLeft = true) => {
  if (node === null) {
    return;
  }
  if (node.right !== null) {
    prettyPrint(node.right, `${prefix}${isLeft ? '│   ' : '    '}`, false);
  }
  console.log(`${prefix}${isLeft ? '└── ' : '┌── '}${node.data}`);
  if (node.left !== null) {
    prettyPrint(node.left, `${prefix}${isLeft ? '    ' : '│   '}`, true);
  }
};

const newTree = tree([1, 2]);
console.log(newTree); // console logs 1 => 2 (right) => 0 (left) even before the newTree.insert(0) line below.
console.log(newTree.insert(0));
console.log(newTree);
// prettyPrint(newTree);

1. 自动插入节点的根源 #

代码里有两个关键错误导致了意外的节点插入：

• 全局变量污染：tree函数中root = buildTree(sortedArr)未用let/const声明，导致root成为全局变量。如果之前运行过insert(0)之类的操作，全局root会被修改，后续创建新树时会继承这个被污染的全局变量。
• insert函数默认参数错误：insert函数里的root = this.root完全不适用——tree是普通工厂函数，不是构造函数，this指向全局对象（浏览器为window，Node.js为global），等于直接操作全局的root变量，进一步加剧了全局污染问题。

2. prettyPrint报错的原因 #

prettyPrint要求传入树的根节点对象，但你调用时传的是整个树实例newTree（包含root和insert方法的对象），函数内部尝试访问node.right时自然会抛出undefined错误。

具体修复步骤 #

（1）修复全局变量问题

给tree函数内的root加上let声明，将其变为局部变量，确保每个树实例的根节点独立：

const tree = (arr) => {
  const sortedArr = mergeSort(removeDuplicates(arr));
  // 用let声明，后续插入操作可更新根节点
  let root = buildTree(sortedArr);
  
  // ... 其他代码
};

（2）重构insert函数逻辑

改用内部递归函数的写法，避免默认参数的陷阱，同时确保只操作当前树实例的根节点：

const insert = (val) => {
  // 内部递归函数，负责遍历插入
  const insertRecursive = (node, val) => {
    if (node === null) {
      return createNode(val);
    }
    // 跳过重复值，符合BST特性
    if (val < node.data) {
      node.left = insertRecursive(node.left, val);
    } else if (val > node.data) {
      node.right = insertRecursive(node.right, val);
    }
    return node;
  };
  // 更新当前树的根节点
  root = insertRecursive(root, val);
};

（3）修复prettyPrint调用方式

传入树实例的根节点而非整个对象：

prettyPrint(newTree.root);

修复后的完整tree函数 #

const tree = (arr) => {
  const sortedArr = mergeSort(removeDuplicates(arr));
  let root = buildTree(sortedArr);
  
  const insert = (val) => {
    const insertRecursive = (node, val) => {
      if (node === null) {
        return createNode(val);
      }
      if (val < node.data) {
        node.left = insertRecursive(node.left, val);
      } else if (val > node.data) {
        node.right = insertRecursive(node.right, val);
      }
      return node;
    };
    root = insertRecursive(root, val);
  };

  return { root, insert };
};

内容的提问来源于stack exchange，提问作者Julian