Warum wird die maximale Größe des Aufruf-Stacks überschritten, wenn ich meinen Baum durchquere?

Question

Ich versuche, den Mindestwert von meinem Binärbaum zu bekommen, aber ich bekomme einen Fehler, dass die maximale Call-Stack-Größe überschritten wurde. Wie erhalte ich den Mindestwert von Elementen in einem binären Suchbaum korrekt?

Hier ist mein Code bei JSBin:

function Node(val){ 
    this.value = val; 
    this.left = null; 
    this.right = null; 
} 

function BinarySearchTree(){ 
    this.root = null; 
} 
BinarySearchTree.prototype.minNode =function() { 
    var node = this.root; 
    if(!node){ 
     return 0; 
    } 
    if(node.left){ 
     return this.minNode(node.left) 
    } 
    return node.value 
} 

BinarySearchTree.prototype.push = function(val){ 
    var root = this.root; 

    if(!root){ 
     this.root = new Node(val); 
     return; 
    } 

    var currentNode = root; 
    var newNode = new Node(val); 

    while(currentNode){ 
     if(val < currentNode.value){ 
      if(!currentNode.left){ 
       currentNode.left = newNode; 
       break; 
      } 
      else{ 
       currentNode = currentNode.left; 
      } 
     } 
     else{ 
      if(!currentNode.right){ 
       currentNode.right = newNode; 
       break; 
      } 
      else{ 
       currentNode = currentNode.right; 
      } 
     } 
    } 

} 

var bt = new BinarySearchTree(); 
bt.push(23); 
bt.push(1); 
bt.push(2); 
bt.push(25); 
console.log(bt.minNode()); 

Answer 1

Wie @AndrewLi erwähnt. Sie sind wieder die gleiche Wurzel Einstellung von

var node = this.root; 

Statt die Definition Ihrer Funktion ändern

BinarySearchTree.prototype.minNode =function(nextNode) { 
    var node = nextNode || this.root; 
    if(!node){ 
     return 0; 
    } 
    if(node.left){ 
     return this.minNode(node.left) 
    } 
    return node.value 
} 

Answer 2

Das Problem ist das Schreiben, dass Sie nicht den Knoten voran, wenn Sie es durchqueren. Sie setzen einfach node auf das Root-Element, so dass es für immer rekursiv ist. Definieren der Funktion wie sollte so funktionieren:

BinarySearchTree.prototype.minNode = function(nextNode) { 
    var node = nextNode || this.root; 
    if(!node) { 
    return 0; 
    } 
    if(node.left) { 
    return this.minNode(node.left) 
    } 
    return node.value 
} 

Dadurch wird die Funktion ein Argument für die nächsten Knoten akzeptieren. Dann wird es node dem nächsten Knoten zuweisen, wenn es existiert, oder dem Stamm, wenn es der erste Aufruf ist. Dies wird nicht für immer rekurrieren, weil es den Baum vorantreibt und durchquert.