BST Structure

A BST node contains three things: a value, a pointer to the left child, and a pointer to the right child. That’s it.

Node Structure

Here’s what a node looks like:

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

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

              class TreeNode {
value: number;
left: TreeNode | null;
right: TreeNode | null;

constructor(value: number) {
  this.value = value;
  this.left = null;
  this.right = null;
}
}
            

Simple, right? The value stores the data. The left and right pointers connect to child nodes, or null if there’s no child.

The BST Property

This is the rule that makes BSTs work:

For any node:

• All values in the left subtree are less than the node’s value
• All values in the right subtree are greater than the node’s value

This rule applies recursively. Every subtree is also a valid BST.

Visual Example

Let’s see a valid BST:

This tree follows the BST property. Check it:

• Root is 50
• Left subtree has 30, 20, 40 (all < 50) ✓
• Right subtree has 70, 60, 80 (all > 50) ✓
• Under 30: 20 < 30 and 40 > 30 ✓
• Under 70: 60 < 70 and 80 > 70 ✓

Invalid BST Example

Here’s what breaks the BST property:

    50
   /  \
  30   70
 / \  / \
20  60 40 80

The problem: 60 is in the left subtree of 50, but 60 > 50. That violates the rule.

Why This Matters

The BST property enables efficient search. When you look for a value:

1. Start at the root
2. Compare with current node
3. If smaller, go left
4. If larger, go right
5. If equal, found it

You eliminate half the tree at each step. That’s why it’s fast.

Balanced vs Unbalanced

A balanced BST has roughly equal nodes on left and right. An unbalanced one looks like a linked list:

Balanced (good):

      50
    /    \
   30    70
  /  \  /  \
 20 40 60 80

Unbalanced (bad):

50
 \
  70
   \
    80
     \
      90

Unbalanced trees lose the O(log n) advantage. They become O(n) in the worst case.

What’s Next?

Now that you understand the structure, let’s learn how to insert nodes while maintaining the BST property.