From the course: Data Structures in JavaScript: Trees and Graphs

Unlock this course with a free trial

Join today to access over 25,500 courses taught by industry experts.

Binary search tree concept

Binary search tree concept

From the course: Data Structures in JavaScript: Trees and Graphs

Start my 1-month free trial Buy for my team

Binary search tree concept

“

- [Instructor] In this lesson, we will talk about binary search trees. A binary search tree, also known as A BST, is a special type of binary tree where the left child's value is less than the parent's value and the right child's value is greater than the parent's value. This structure allows for efficient search, insertion and deletion operations with an average time complexity of big O(log n). I say average time complexity because in the worst case, big O(n) happens when the tree is unbalanced and reduced to a linked list. In that case, each insertion walks through n number of nodes. Depending on the implementation, the space complexity for these operations is either big O(1) for the iterative approach or big O(h) for the recursive approach where h is the height of the tree. Unlike a general binary tree, a BSTs organization where all nodes in the left subtree are less than the root node and all nodes in the right subtree are greater ensures that operations like search, insertion and…

Contents