Binary Search Trees - Part II/?

Welcome to part two of this series of indeterminate length, where I attempt to break down Binary Search Trees into manageable bits. In Part I, I went over what a Binary Search Tree is, and the different forms they can take. In Part II we'll look at how to represent one in code - which turns out to be pretty easy!

Ultimately all you need to represent a binary search tree in code is a "Node" class. Each node will have three properties - data, a left child, and a right child. Each child will also be a node, with its own children. If it does not have any children, they will simply be listed as null.

Below is an example implementation of this class in JavaScript:

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

In order to make a really functional binary search tree, though, you of course need to make some functions to go along with! If it were me, I'd encapsulate all those into a nice, neat, wrapper class. We can just call it BinarySearchTree.

Inside that class we can include functions for adding and removing nodes, for accessing the root, for determining if a node exists, all sorts of things. Here is an example class with a few sample functions blocked in:

// Tree Class
class BinarySearchTree 
{ 
    constructor() 
    { 
        // root of a binary search tree 
        //while currently null, will be a node once you start filling the tree!
        this.root = null;     
    } 


    // functions:

    // insert(data) 
    // remove(data) 


    // Helper functions
    // findMinNode() 
    // getRootNode()
    // search(data) 
} 

We'll cover implementing these functions in future posts, since other than getRoodNode() they are all pretty complex.

Part II turned out to be pretty short! Next time, adding and removing nodes, and what to do with duplicates.