SimuVedaAlgorithms Lab Open in the lab

Trees / Beginner

BST Insert Visualizer

Start at the root. Go left if the new value is smaller, right if bigger, until you reach an empty spot.

Start the BST Insert simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(log n)
Average timeO(log n)
Worst timeO(n)
Extra spaceO(h)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Insert 45.
  2. Compare 45 with 50.
  3. 45 < 50, so go left.
  4. Compare 45 with 30.
  5. 45 > 30, so go right.
  6. Compare 45 with 40.
  7. 45 > 40 and the right spot is empty. Place 45 there.

Try it with your own input →

BST insert in Java, Python, C++, C and JavaScript

Node insert(Node root, int val) {
  if (root == null) return new Node(val);
  if (val < root.val)
    root.left = insert(root.left, val);
  else if (val > root.val)
    root.right = insert(root.right, val);
  return root;
}
def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root
Node* insert(Node* root, int val) {
  if (!root) return new Node(val);
  if (val < root->val)
    root->left = insert(root->left, val);
  else if (val > root->val)
    root->right = insert(root->right, val);
  return root;
}
struct Node* insert(struct Node* root, int val) {
  if (root == NULL) return newNode(val);
  if (val < root->val)
    root->left = insert(root->left, val);
  else if (val > root->val)
    root->right = insert(root->right, val);
  return root;
}
function insert(root, val) {
  if (root === null) return { val, left: null, right: null };
  if (val < root.val)
    root.left = insert(root.left, val);
  else if (val > root.val)
    root.right = insert(root.right, val);
  return root;
}

In an interview

Load 10, 20, 30, 40, 50 as values: the tree turns into a straight line and every operation becomes O(n). That is why balanced trees (AVL, red-black) exist.

More trees