Recursion

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(\log n)$ time, which is better than a Sorted Array's $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(\log n)$, assuming the tree is balanced. Balanced trees have a height of $O(\log n)$, and you need to step to the bottom of the tree worst-case.

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

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

Create Time Complexity $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(n \log n)$.

More details:

There are ways of keeping a BST balanced at all times, called "self-balancing BSTs". Questions about them are not very common in interviews, though.

Comparison between Sorted Array and BST:

$\notag
\def\t#1{\text{#1}}
\def\ss{\;\;\;\;\;\;\;\;}
\begin{align*}
&\t{}
&\t{Sorted Array}\ss
&\t{Balanced BST} \\[10bp]
&\text{Search Time}
&\t{O(log n)}\ss
&\t{O(log n)} \\
&\t{Read Time}
&\t{O(1)}\ss\;\;\;\;\;
&\t{O(log n)} \\
&\t{Insert/Delete Time}
&\t{O(n)}\ss\;\;\;\;\;
&\t{O(log n)} \\
\end{align*}$

Mark as Completed: