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:
-
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).
-
Left Child Pointer: A reference to the left subtree's root node. If there's no left child, this pointer is
null. -
Right Child Pointer: A reference to the right subtree's root node. If there's no right child, this pointer is
null. -
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.