BST Insert

tree

Click Generate New or press Play

Step 1 / 1

Ready

Speed

Inserts a new value into a Binary Search Tree by finding the correct position.

Time Complexity

Best

\mathrm{O}\left(\log n\right)

Avg

\mathrm{O}\left(\log n\right)

Worst

\mathrm{O}\left(n\right)

Space Complexity

Aux

\mathrm{O}\left(h\right)

Recursive call stack — O(log n) avg, O(n) worst

Pseudocode

1procedure insert(node, value)

2if node is null then return new Node(value)

3if value < node.value then

4node.left = insert(node.left, value)

5else node.right = insert(node.right, value)

6return node