Algorithm

Binary Search Tree Insertion

tree

BST Insertion adds a new node to a Binary Search Tree while maintaining the essential BST property: all values in any node's left subtree are less than the node's value, and all values in the right subtree are greater. The algorithm traverses the tree starting from the root, making comparisons at each node to determine whether to go left or right. When it reaches a null pointer, it creates a new node in that position. This process leverages the BST structure to achieve O(log n) insertion time in balanced trees. However, in worst cases (like inserting already-sorted data), the tree can degenerate into a linked list, degrading performance to O(n). BST insertion is fundamental to building search trees and supports operations like finding minimum/maximum values, successor/predecessor relationships, and maintaining sorted data in a dynamic structure that allows for efficient insertions and deletions.

Time: O(log n) average, O(n) worst case
Space: O(h) where h is the height of the tree

Visualization

Step 1 of 0

Controls & Input

1x

Implementation

Pseudocode

0 function insert(root, value):
1 if root is null:
2 return new Node(value)
3
4 // Compare with current node
5 if value < root.value:
6 // Insert into left subtree
7 if root.left is null:
8 root.left = new Node(value)
9 else:
10 root.left = insert(root.left, value)
11
12 else if value > root.value:
13 // Insert into right subtree
14 if root.right is null:
15 root.right = new Node(value)
16 else:
17 root.right = insert(root.right, value)
18
19 // Value already exists, do nothing
20 else:
21 // Value already exists in the tree
22
23 return root