A Binary Search Tree

This JavaScript Reference section displays the code for an example program that shows how to create a binary search tree in JavaScript.

BinarySearchTree.html

<!DOCTYPE html>
<html>
	<head>
	    <title>XoaX.net's Javascript</title>
	    <script type="text/javascript" src="BinarySearchTree.js"></script>
	</head>
	<body onload="fnInitialization()">
	</body>
</html>

BinarySearchTree.js

// The Tree Node Constructor
function CNode(qData) {
  this.mqData = qData;
  this.mqpParent = null;
  this.mqpLeft   = null;
  this.mqpRight  = null;

  this.mfnNextHighest = function() {
    var qpNext = null;
    if (this.mqpRight != null) { // If there is a right child,
      // the next highest is the least beneath the right child
	  var qpNext = this.mqpRight;
	  while (qpNext.mqpLeft != null) {
        qpNext = qpNext.mqpLeft;
	  }
	} else {
      // If there is no right child, the next highest is the first ancester
      // that that has a left child above this node.
      var qpChild = this;
      var qpNext = qpChild.mqpParent;
      while (qpNext != null && qpNext.mqpRight == qpChild) {
		qpNext = qpNext.mqpParent;
	  }
	}
	return qpNext;
  }
  // Replace the node in its position, using the new data
  this.mfnReplaceNode = function(qpNodeToReplace) {
	this.mqpParent = qpNodeToReplace.mqpParent;
	this.mqpLeft   = qpNodeToReplace.mqpLeft;
	this.mqpRight  = qpNodeToReplace.mqpRight;
    if (this.mqpParent != null) {
      // It is either a left of right child
      if (this.mqpParent.mqpLeft == qpNodeToReplace) {
        this.mqpParent.mqpLeft = this;
	  } else {
        this.mqpParent.mqpRight = this;
	  }
  	}
    if (this.mqpLeft != null) {
      this.mqpLeft.mqpParent = this;
  	}
    if (this.mqpRight != null) {
      this.mqpRight.mqpParent = this;
  	}
  }
  this.mfnProcessInOrder = function(fnProcessor) {
    if (this.mqpLeft != null) {
      this.mqpLeft.mfnProcessInOrder(fnProcessor);
  	}
  	fnProcessor(this.mqData);
    if (this.mqpRight != null) {
      this.mqpRight.mfnProcessInOrder(fnProcessor);
  	}
  }
  this.mfnInsertLeftChild = function(qpNode) {
    qpNode.mqpParent = this;
    qpNode.mqpLeft = this.mqpLeft;
    this.mqpLeft = qpNode;
  }
  this.mfnInsertRightChild = function(qpNode) {
    qpNode.mqpParent = this;
    qpNode.mqpRight = this.mqpRight;
    this.mqpRight = qpNode;
  }
  this.mfnDisplayNodeValue = function(sNodeName, qContainer) {
    // The name is a binary number indicating position: 0 = left, 1 = right
    // Try to get the element for this node.
    var qpDisplayElement = document.getElementById(sNodeName);
    // Check whether the element exists. If not, create the whole row.
    if (qpDisplayElement == null) {
      // The length of the string tells us how many elements are at this level.
      var iStringLength = sNodeName.length;
      // If the length is 3, there are 2^(3 - 1)  = 4 elements at this level
      var iElementCount = (1 << (iStringLength - 1));
      var dWidthPercent = ((100)/iElementCount);
      for (var i = 0; i < iElementCount; ++i) {
        var iNameValue = (iElementCount + i);
        var sName = "";
        var iBit = iElementCount;
        while (iBit > 0) {
          sName += ((iBit & iNameValue) ? "1" : "0");
          iBit >>= 1;
        }
        // Create a div
        var qDiv = document.createElement("div");
        var qAttribute = document.createAttribute("id");
        qAttribute.value = sName;
        qDiv.setAttributeNode(qAttribute);
        qDiv.style.float = "left";
        qDiv.style.width = (dWidthPercent-.25) + "%";
        qDiv.style.height = "25px";
        qDiv.style.textAlign = "center";
        qDiv.style.paddingTop = "7px";
        qDiv.style.margin = ".125%";
        // Add the element to the container.
        qContainer.appendChild(qDiv);
	  }
	  qpDisplayElement = document.getElementById(sNodeName);
	}
	qpDisplayElement.style.color = "black";
	qpDisplayElement.style.backgroundColor = "LightGray";
	qpDisplayElement.innerHTML = this.mqData;
	// Call it on the children, if they exist
	if (this.mqpLeft != null) {
      this.mqpLeft.mfnDisplayNodeValue(sNodeName+"0", qContainer);
	}
	if (this.mqpRight != null) {
      this.mqpRight.mfnDisplayNodeValue(sNodeName+"1", qContainer);
	}
  }
}

// The Binary Search Tree Constructor
function CBinarySearchTree() {
  this.mqpRoot = null;
  this.mfnInsert = function(qData) {
    if (this.mfnIsEmpty()) {
      this.mqpRoot = new CNode(qData);
	} else {
      var qpCurr = this.mqpRoot;
      var bInserted = false;
      while(!bInserted) {
        if (qData < qpCurr.mqData) {
          if (qpCurr.mqpLeft == null) {
            qpCurr.mfnInsertLeftChild(new CNode(qData));
            bInserted = true;
          } else {
            qpCurr = qpCurr.mqpLeft;
          }
        } else {
          if (qpCurr.mqpRight == null) {
            qpCurr.mfnInsertRightChild(new CNode(qData));
            bInserted = true;
          } else {
            qpCurr = qpCurr.mqpRight;
          }
        }
      }
    }
  }
  this.mfnDelete = function(qpNode) {
    var qpY = null;
    if (qpNode.mqpLeft == null || qpNode.mqpRight == null) {
      qpY = qpNode;
    } else {
      // We really only need this for right children
      qpY = qpNode.mfnNextHighest();
    }
    var qpX = ((qpY.mqpLeft != null) ? qpY.mqpLeft : qpY.mqpRight);
    if (qpX != null) {
      qpX.mqpParent = qpY.mqpParent;
    }
    // This only happens if we are deleting the root
    if (qpY.mqpParent == null) {
      this.mqpRoot = qpX;
    } else if (qpY == qpY.mqpParent.mqpLeft) {
      qpY.mqpParent.mqpLeft = qpX;
    } else {
      qpY.mqpParent.mqpRight = qpX;
    }
    if (qpY != qpNode) {
      if (this.mqpRoot == qpNode) {
        this.mqpRoot = qpY;
      }
      // This will copy everything except the data
      qpY.mfnReplaceNode(qpNode);
      // Now qpNode is deleted.
	}
  }
  this.mfFind = function(qData) {
    var qpCurr = this.mqpRoot;
    while (qpCurr != null) {
      if (qData < qpCurr.mqData) {
        qpCurr = qpCurr.mqpLeft;
      } else if(qData > qpCurr.mqData) {
        qpCurr = qpCurr.mqpRight;
      } else {
        return qpCurr;
      }
	}
	return null;
  }
  this.mfDisplay = function(qContainerElement) {
    // The position can be determined by this string
    var sRootNodeName = "1";
    if (this.mqpRoot != null) {
    this.mqpRoot.mfnDisplayNodeValue(sRootNodeName, qContainerElement);
    }
  }
  this.mfProcessInOrder = function(fnProcessor) {
	if (!this.mfnIsEmpty()) {
      this.mqpRoot.mfnProcessInOrder(fnProcessor);
    }
  }
  this.mfnIsEmpty = function() {
    return (this.mqpRoot == null);
  }
}


function fnPrint(qData) {
  var qpPrint = document.getElementById("idOutput");
  qpPrint.innerHTML += qData + " ";
}

function fnInitialization() {
  var qBinarySearchTree = new CBinarySearchTree();

  // Insert 12 random values
  for (var i = 0; i < 12; ++i) {
	  qBinarySearchTree.mfnInsert(Math.round((Math.random()*30)));
  }

  var qDisplayDiv = document.createElement("div");
  qDisplayDiv.style.width = "800px";
  qDisplayDiv.style.height = "350px";
  qDisplayDiv.style.border = "black 1px solid";
  qDisplayDiv.style.backgroundColor = "WhiteSmoke";
  document.body.appendChild(qDisplayDiv);

  // Delete 12 random values, which may or may not be present
  for (var i = 0; i < 12; ++i) {
    var qpDeleteNode = qBinarySearchTree.mfFind(Math.round((Math.random()*30)));
    if (qpDeleteNode != null) {
      qBinarySearchTree.mfnDelete(qpDeleteNode);
    }
  }

  qBinarySearchTree.mfDisplay(qDisplayDiv);
}