BST Insert — VisualAlgorithms Docs

How it works

Insert a key into a binary search tree, descending left for smaller keys and right for larger.
Implementation

      
 function bstInsertOp(state, value) {
  const keys = state.keys;
  const left = state.left;
  const right = state.right;
  if (state.root === -1) {
    const id = keys.length;
    keys[id] = value;
    left[id] = -1;
    right[id] = -1;
    state.root = id;
    insertNode(id, value);
    finish(id);
    return;
  }
  let current = state.root;
  while (current !== -1) {
    compareKeys(current, value);
    if (value < keys[current]) {
      if (left[current] === -1) {
        const id = keys.length;
        keys[id] = value;
        left[id] = -1;
        right[id] = -1;
        left[current] = id;
        linkNodes(current, id);
        insertNode(id, value);
        finish(id);
        return;
      }
      current = left[current];
    } else {
      if (right[current] === -1) {
        const id = keys.length;
        keys[id] = value;
        left[id] = -1;
        right[id] = -1;
        right[current] = id;
        linkNodes(current, id);
        insertNode(id, value);
        finish(id);
        return;
      }
      current = right[current];
    }
  }
} def bstInsertOp(state, value):
    keys = state.keys
    left = state.left
    right = state.right
    if (state.root == -1):
        id = keys.length
        keys[id] = value
        left[id] = -1
        right[id] = -1
        state.root = id
        insertNode(id, value)
        finish(id)
        return
    current = state.root
    while (current != -1):
        compareKeys(current, value)
        if (value < keys[current]):
            if (left[current] == -1):
                id = keys.length
                keys[id] = value
                left[id] = -1
                right[id] = -1
                left[current] = id
                linkNodes(current, id)
                insertNode(id, value)
                finish(id)
                return
            current = left[current]
        else:
            if (right[current] == -1):
                id = keys.length
                keys[id] = value
                left[id] = -1
                right[id] = -1
                right[current] = id
                linkNodes(current, id)
                insertNode(id, value)
                finish(id)
                return
            current = right[current] #include <vector>
#include <algorithm>
void bstInsertOp(int state, int value) {
    auto keys = state.keys;
    auto left = state.left;
    auto right = state.right;
    if((state.root == -1)) {
        auto id = keys.length;
        keys[id] = value;
        left[id] = -1;
        right[id] = -1;
        state.root = id;
        insertNode(id, value);
        finish(id);
        return;
    }
    auto current = state.root;
    while((current != -1)) {
        compareKeys(current, value);
        if((value < keys[current])) {
            if((left[current] == -1)) {
                auto id = keys.length;
                keys[id] = value;
                left[id] = -1;
                right[id] = -1;
                left[current] = id;
                linkNodes(current, id);
                insertNode(id, value);
                finish(id);
                return;
            }
            current = left[current];
        } else {
            if((right[current] == -1)) {
                auto id = keys.length;
                keys[id] = value;
                left[id] = -1;
                right[id] = -1;
                right[current] = id;
                linkNodes(current, id);
                insertNode(id, value);
                finish(id);
                return;
            }
            current = right[current];
        }
    }
} public void bstInsertOp(int state, int value) {
    var keys = state.keys;
    var left = state.left;
    var right = state.right;
    if((state.root == -1)) {
        var id = keys.length;
        keys[id] = value;
        left[id] = -1;
        right[id] = -1;
        state.root = id;
        insertNode(id, value);
        finish(id);
        return;
    }
    var current = state.root;
    while((current != -1)) {
        compareKeys(current, value);
        if((value < keys[current])) {
            if((left[current] == -1)) {
                var id = keys.length;
                keys[id] = value;
                left[id] = -1;
                right[id] = -1;
                left[current] = id;
                linkNodes(current, id);
                insertNode(id, value);
                finish(id);
                return;
            }
            current = left[current];
        } else {
            if((right[current] == -1)) {
                var id = keys.length;
                keys[id] = value;
                left[id] = -1;
                right[id] = -1;
                right[current] = id;
                linkNodes(current, id);
                insertNode(id, value);
                finish(id);
                return;
            }
            current = right[current];
        }
    }
} #include <stdio.h>
void bstInsertOp(int state, int value) {
    var keys = state.keys;
    var left = state.left;
    var right = state.right;
    if((state.root == -1)) {
        var id = keys.length;
        keys[id] = value;
        left[id] = -1;
        right[id] = -1;
        state.root = id;
        insertNode(id, value);
        finish(id);
        return;
    }
    var current = state.root;
    while((current != -1)) {
        compareKeys(current, value);
        if((value < keys[current])) {
            if((left[current] == -1)) {
                var id = keys.length;
                keys[id] = value;
                left[id] = -1;
                right[id] = -1;
                left[current] = id;
                linkNodes(current, id);
                insertNode(id, value);
                finish(id);
                return;
            }
            current = left[current];
        } else {
            if((right[current] == -1)) {
                var id = keys.length;
                keys[id] = value;
                left[id] = -1;
                right[id] = -1;
                right[current] = id;
                linkNodes(current, id);
                insertNode(id, value);
                finish(id);
                return;
            }
            current = right[current];
        }
    }
} 