Recursion

Binary Search Tree

Lesson

A Binary Search Tree is just a Sorted Array, but in the shape of a tree. This lets you insert/delete elements in O(logn)O(\log n) time, which is better than a Sorted Array's O(n)O(n) insert/delete time.

You traverse a Binary Search Tree in the exact order that you'd do a Binary Search, hence the name. You can try this out below yourself. Use a Binary Search to find the number 3 in the sorted array, and then in the BST:

The definition of a BST is that the values in the left subtree are all smaller than the current value, and the values in the right subtree are all larger than the current value.

Question: Is the value "7" allowed where the arrow is drawn in the below tree?

Answer:

Search Time Complexity O(logn)O(\log n), assuming the tree is balanced. Balanced trees have a height of O(logn)O(\log n), and you need to step to the bottom of the tree worst-case.

Read Time Complexity O(logn)O(\log n), assuming the tree is balanced.

Insert/Delete Time Complexity O(logn)O(\log n), assuming the tree is balanced.

Create Time Complexity O(nlogn)O(n \log n). You can sort your elements and then turn the sorted array into a BST, or you can add elements to an empty BST one at a time. Either way, this is O(nlogn)O(n \log n).

More details:

Mark as Completed:
Submits:
test
Test your code to get an output here!