Функция вставки бинарного дерева поиска не может добавить новый узел в дерево

Question

Я пишу код для реализации бинарного дерева поиска в Python.Я столкнулся с проблемами при написании функции insert, которая должна добавить новый узел в правильном порядке расположения в дереве.Я написал это двумя разными способами: insertNode1 работает нормально (правильно выполняет вставку в дерево), но insertNode2 не выполняет вставку должным образом.Когда я выполняю InOrderTraversal для дерева, используя insertNode1 и insertNode2, оказалось, что «insertNode1» возвращает полное дерево, а «insertNode2» - только корень.

Почему insertNode1 преуспевает, в то время как insertNode2 терпит неудачу, и каковы значимые различия между двумя функциями, которые приводят к этому?

Вот мой код:

def insert(self,val):
    if not self.root:
      self.root = TreeNode(val)
    else:
      self.insertNode2(self.root, val)

  def insertNode1(self,node, val):
    if val < node.val:
      if not node.left:
        node.left = TreeNode(val)
      else:
        self.insertNode1(node.left,val)
    else:
      if not node.right:
        node.right = TreeNode(val)
      else:
        self.insertNode1(node.right, val)

  def insertNode2(self, node, val):
    if not node:
      node = TreeNode(val)
    else:
      if node.val > val:
        self.insertNode2(node.left, val)
      else:
        self.insertNode2(node.right, val)

Answer 1

insertNode2 неправильно выполняет вставку, как ожидалось, из-за строки node = TreeNode(val), которая делает чисто локальное присвоение node.Этот новый объект никогда не устанавливается в родительское свойство .left или .right и теряется при возврате функции.Корневой узел не будет изменен ни при каком запуске этой функции.

Либо используйте уже работающий insertNode1, либо добавьте оператор return node к insertNode2 и сделайте присваивание в вызове родительской функциипростор для нового ребенка.

Вот фрагмент, демонстрирующий, как это можно сделать:

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BinarySearchTree:
    @staticmethod
    def p(root, depth=0):
        if root:
            print(" " * depth + str(root.val))
            BinarySearchTree.p(root.left, depth + 2)
            BinarySearchTree.p(root.right, depth + 2)

    @staticmethod
    def insert(node, val):
        if not node:
            return TreeNode(val)    
        elif node.val > val:
            node.left = BinarySearchTree.insert(node.left, val)
        else:
            node.right = BinarySearchTree.insert(node.right, val)

        return node

if __name__ == "__main__":
    root = TreeNode(5)

    for n in [2, 1, 3, 7, 9, 6]:
        BinarySearchTree.insert(root, n)

    BinarySearchTree.p(root)

Вывод:

5
  2
    1
    3
  7
    6
    9

Что составляет: