Binary Trees and Binary Search Trees: The Invariant That Makes Search Work

Introduction

A binary search tree is useful because every node follows one ordering rule: smaller values go left and larger values go right. Search works by trusting that rule. For example, when searching for 13 in a tree whose root is 20, the search can immediately move left because 13 is smaller than 20.

Start with the shape

A binary tree is a collection of nodes where each node has at most two child references. A node is one object that stores a value and links to its children. The references are conventionally called left and right; they do not automatically impose an ordering. A binary search tree (BST) adds a rule: values in the left subtree compare lower than the node, and values in the right subtree compare higher.

That rule is the invariant, meaning a condition that should remain true after the tree is built or changed. It is what lets a search discard one side of the remaining tree at each comparison. Without it, the structure is still a binary tree, but finding a value may require visiting every node.

A subtree is a node together with all of the nodes below it. The root is the first node in the tree, and a leaf is a node with no children.

The Binary-Search-Tree repository represents a node with data, left, and right. A Tree stores the root. The fields are ordinary object properties, and an empty child is represented by null.

How this repository builds its tree

The constructor calls buildTree(array). The method removes duplicates with Set, sorts the remaining numbers numerically, and recursively chooses the middle element of each range. The chosen value becomes a node; the left and right ranges become its child subtrees.

This means the repository's duplicate policy is explicit: duplicate input values are ignored during construction, and insert also leaves an existing value unchanged. The midpoint construction gives the initial tree similar-sized subproblems, although later insertions can make its shape uneven.

This is documented behavior from the README and source. It is different from claiming that every BST is balanced: the tree can become skewed after ordinary inserts.

Following one search path

Consider the tree in the diagram and search for 13:

1. Compare 13 with 20. It is lower, so follow left.
2. Compare it with 10. It is higher, so follow right.
3. Compare it with 13. The node is found.

At each step, the invariant tells us which child can still contain the value. Searching an unsorted array cannot make that decision from one comparison; it scans candidates until it finds a match or reaches the end. This is the main advantage of the BST structure, provided that its ordering rule has been preserved.

The repository's find(value) implements this path recursively and returns the node or null. depth(value) counts edges from the root and warns, returning undefined, when the value is absent.

Insertion preserves the rule

insert(value) calls a recursive helper. A null position becomes a new node. A lower value recurses left, a higher value recurses right, and an equal value takes neither branch. Each recursive call returns its subtree root, allowing the parent link to be updated as the call unwinds.

The important invariant after insertion is local and global at once: the new node is placed only where every ancestor comparison permits it. A chain of increasing inserts can still produce a long right-leaning tree; ordering does not guarantee balance.

Four traversals, four useful views

The repository exposes four traversals and passes each visited value to a callback, which is a function supplied to run for every visited node:

In the current source, level order uses an array queue and front index. The depth-first traversals are the recursive implementations; iterative versions remain in the file but are not the methods currently called. Each public traversal validates that the callback is a function and reports an error otherwise.

For the example tree, a reproducible run gives these value orders:

const tree = new Tree([20, 10, 30, 5, 13, 25, 40]);

const values = [];
tree.inOrder(value => values.push(value));
console.log(values); // [5, 10, 13, 20, 25, 30, 40]

That sorted result is not a property of inorder traversal alone. It follows because the tree satisfies the BST ordering rule.

Height, depth, and shape

The source defines an empty subtree's height as -1, so a leaf has height 0. Height is the number of edges in the longest path from a node down to a leaf. height() follows the larger child height plus one. depth(value) measures the number of edges on the search path from the root.

For a roughly balanced tree, a search path is proportional to log n. For a skewed tree, the path can be proportional to n, similar to a linked list. The repository includes isBalanced() and rebalance(), but those are separate operations from the basic BST invariant: a tree can be a valid BST without being balanced.

Complexity with the relevant assumptions

Let n be the number of nodes and h the tree height.

The O(log n) description for search applies when h grows logarithmically. It is not a promise made by the data structure in every shape.

What I would keep in mind

The project made the invariant easier to see because every operation can be explained as preserving or using one comparison rule. It also made the cost of shape visible: midpoint construction starts from a helpful shape, while arbitrary insertion order can gradually remove that advantage.

The repository uses numeric comparison and ignores duplicates. A different application could define another comparison policy, but it would need to apply that policy consistently in construction, insertion, searching, and deletion.

Key takeaways

• A binary tree limits children to left and right; a BST additionally orders values around every node.
• The ordering invariant is what lets search choose one child instead of scanning both.
• This repository removes duplicates, builds its initial tree from sorted unique values, and chooses midpoint roots.
• Inorder traversal produces sorted output because the BST invariant holds.
• Search costs O(h): logarithmic for a balanced shape and linear for a skewed one.

Sources

• Author repository: Binary-Search-Tree
• Tree implementation
• The Odin Project: Binary Search Trees
• Open Data Structures