Course contentsShow
← Computer Science
Lesson 497 of 2,87212. Binary Search TreesFree lesson

BST Node Structure

Define the node structure: key/value, left child pointer, right child pointer, optional parent pointer.

BST Node Structure

What you'll learn: How a binary search tree node is built using pointers and data fields to maintain the BST property.


The Building Block of a BST

Every binary search tree is composed of nodes. Each node is a container that holds data and maintains connections to other nodes, forming the tree structure. Understanding the node structure is essential before implementing any BST operations.

The Core Components

A BST node contains:

  1. Key/Value: The data stored in the node. The key determines the node's position and must satisfy the BST invariant (left children < parent < right children). Sometimes you store just a key, other times a key-value pair (like in a dictionary).

  2. Left Child Pointer: A reference to the left subtree's root node. If there's no left child, this pointer is null.

  3. Right Child Pointer: A reference to the right subtree's root node. If there's no right child, this pointer is null.

  4. Parent Pointer (Optional): Some implementations include a pointer back to the parent node. This makes certain operations easier (like finding successors) but uses extra memory.

Visualizing the Structure

Think of a node as a junction box with three wires coming out: one going left, one going right, and optionally one going up to the parent. The box itself holds your data.

      [key: 50]
       /    \
    left   right

With or Without Parent Pointers?

Without parent: Simpler, uses less memory. Most basic BST implementations work this way.

With parent: Makes traversing upward easier and simplifies certain algorithms (like deletion), but adds complexity and memory overhead.

Key Takeaway: A BST node minimally contains a key/value and two child pointers (left and right); parent pointers are optional and trade memory for convenience in certain operations.