Data Structure: Binary Search Tree(BST)

Binary Search Tree or BST is a special type of tree that is used for organizing data in a way that searching becomes easier. The rule is simple for BST-

Everything on the left of the node is smaller than the selected node.
Everything on the right of the node is larger than the selected node.

NOTE

In this article, we are discussing in detail, the implementation of Binary Search Tree(BST) in JavaScript and TypeScript.

Check the link below to check the details of Binary Search Tree(BST)-

Binary Search Tree(BST) Details

Implementation #1: Simple Implementation

Let’s go with the simple approach, to implement Binary Search tree-

Output:

----------- BST insert example -----------

Insert - 100 | Result:  BinarySearchTree { root: Node { data: 100, left: null, right: null } }
Insert - 40 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: null },
    right: null
  }
}
Insert - 60 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: null
  }
}
Insert - 190 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: null, right: null }
  }
}
Insert - 110 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
Insert - 150 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
Insert - 120 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
Insert - 100 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}


----------- BST search example -----------

Node {
  data: 150,
  left: Node { data: 120, left: null, right: null },
  right: null
}

Implementation #2: With Recursion

In this approach we are using recursion in our code, to make the code easier to implement and read-

Step #1: Node Class

The Node class will be same. We have no change here.

JavaScript
TypeScript

Step #2: BinarySearchTree Class

The BinarySearchTree has the same property as the simple approach, no change here.

JavaScript
TypeScript

Step #4: Search Operation

JavaScript

TypeScript

Full Source Code

JavaScript
TypeScript

Demo

JavaScript
TypeScript

Output:

----------- BST insert example -----------

Insert - 100 | Result:  BinarySearchTree { root: Node { data: 100, left: null, right: null } }
Insert - 40 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: null },
    right: null
  }
}
Insert - 60 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: null
  }
}
Insert - 190 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: null, right: null }
  }
}
Insert - 110 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
Insert - 150 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
Insert - 120 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
Insert - 100 | Result:  BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}
BinarySearchTree {
  root: Node {
    data: 100,
    left: Node { data: 40, left: null, right: [Node] },
    right: Node { data: 190, left: [Node], right: null }
  }
}


----------- BST search example -----------

Node {
  data: 150,
  left: Node { data: 120, left: null, right: null },
  right: null
}
null
Node { data: 60, left: null, right: null }

Time Complexity

Operation	Complexity
Insert	O(log(n))
Search	O(log(n))

Source Code

Use the following links to get the source code used in this article-

Source Code of	Implementation Code	Demo Code	Test Code
JavaScript Implementation	GitHub	GitHub	GitHub
TypeScript Implementation	GitHub	GitHub	GitHub

Related Data Structures

Command	Details
Singly Linked List	Singly Linked List Detail

Other Code Implementations

Use the following links to check the Binary Search Tree(BST) implementation in other programming languages-