Tree examples

These examples implement a binary search tree, insert values, search for present and missing values, and traverse the tree in order.

Python

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)

    def _insert(self, node, value):
        if node is None:
            return Node(value)
        if value < node.value:
            node.left = self._insert(node.left, value)
        elif value > node.value:
            node.right = self._insert(node.right, value)
        return node

    def contains(self, value):
        current = self.root
        while current is not None:
            if value == current.value:
                return True
            current = current.left if value < current.value else current.right
        return False

    def inorder(self):
        values = []

        def visit(node):
            if node is None:
                return
            visit(node.left)
            values.append(node.value)
            visit(node.right)

        visit(self.root)
        return values


def print_label_value(label, value):
    print(f"\033[1;36m{label}:\033[0m {value}")


tree = BinarySearchTree()
for index, value in enumerate([8, 3, 10, 1, 6, 14], start=1):
    tree.insert(value)
    print_label_value(f"{index}. Insert {value}", "done")

print_label_value("7. Search 6", "found" if tree.contains(6) else "not found")
print_label_value("8. Search 7", "found" if tree.contains(7) else "not found")
print_label_value("9. In-order traversal", " -> ".join(map(str, tree.inorder())))

JavaScript

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  insert(value) {
    this.root = this.insertNode(this.root, value);
  }

  insertNode(node, value) {
    if (node === null) {
      return new Node(value);
    }
    if (value < node.value) {
      node.left = this.insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this.insertNode(node.right, value);
    }
    return node;
  }

  contains(value) {
    let current = this.root;
    while (current !== null) {
      if (value === current.value) {
        return true;
      }
      current = value < current.value ? current.left : current.right;
    }
    return false;
  }

  inorder() {
    const values = [];
    const visit = (node) => {
      if (node === null) {
        return;
      }
      visit(node.left);
      values.push(node.value);
      visit(node.right);
    };
    visit(this.root);
    return values;
  }
}

function printLabelValue(label, value) {
  console.log(`\x1b[1;36m${label}:\x1b[0m`, value);
}

const tree = new BinarySearchTree();
[8, 3, 10, 1, 6, 14].forEach((value, index) => {
  tree.insert(value);
  printLabelValue(`${index + 1}. Insert ${value}`, "done");
});

printLabelValue("7. Search 6", tree.contains(6) ? "found" : "not found");
printLabelValue("8. Search 7", tree.contains(7) ? "found" : "not found");
printLabelValue("9. In-order traversal", tree.inorder().join(" -> "));

Expected output

1. Insert 8: done
2. Insert 3: done
3. Insert 10: done
4. Insert 1: done
5. Insert 6: done
6. Insert 14: done
7. Search 6: found
8. Search 7: not found
9. In-order traversal: 1 -> 3 -> 6 -> 8 -> 10 -> 14