Binary Trees: Structure, Traversal, and Operations — Topics & Learning Outcomes

Module Topics

Introduction to Binary Trees

• What Is a Binary Tree? — A binary tree is a hierarchical data structure composed of nodes connected by edges, where each node holds a value and links to at most two child nodes.
• Nodes and Edges — Nodes are the fundamental units of a binary tree, each storing a data value and references to its children, while edges are the directional links connecting a parent node to a child node.
• The Root Node — The root is the single topmost node of a binary tree and serves as the unique entry point through which all other nodes are reachable.
• Leaf Nodes — A leaf node is any node that has no children — both its left and right child references are null — representing the endpoints of the tree.
• Parent-Child Relationships — In a binary tree, every node except the root has exactly one parent, and each node can be the parent of zero, one, or two children, forming a strict hierarchical relationship.
• The Binary Constraint: Structural Rules — The defining rule of a binary tree is that every node may have at most two children, conventionally referred to as the left child and the right child.

Node Structure and Tree Anatomy

• Anatomy of a Binary Tree Node — A binary tree node is the fundamental building block of the tree structure, containing three core components: a data field and two child references.
• Root, Parent, and Child Relationships — Binary trees are organized through hierarchical relationships between nodes, starting from a single entry point called the root.
• Node Depth — Depth measures how far a specific node is from the root of the tree, providing a way to locate nodes within the hierarchy.
• Tree Height — Height is a property that describes the overall size of a tree or subtree, measured as the longest path from a node down to a leaf.
• Subtrees and Tree Levels — A binary tree can be understood recursively as a root node connected to a left subtree and a right subtree, each of which is itself a binary tree.
• Tree Balance — Balance refers to how evenly the nodes of a tree are distributed between left and right subtrees, directly impacting the performance of tree operations.

Binary Search Trees (BST) Concepts

• The BST Ordering Property — A Binary Search Tree is a specialized binary tree that enforces a strict ordering rule on every node in the structure.
• BST Node Structure — Each node in a Binary Search Tree holds a value and references to its left and right children, forming the backbone of the tree.
• How BST Ordering Enables Efficient Search — The ordering property of a BST allows search operations to eliminate half of the remaining nodes at each step, similar to a binary search on a sorted array.
• BST vs. General Binary Tree — While all BSTs are binary trees, not all binary trees are BSTs — the key distinction lies in the presence of the ordering constraint.
• BST Height and Performance — The efficiency of BST operations is directly tied to the height of the tree, which depends on the order in which values are inserted.

Insertion and Search Operations

• BST Ordering Property — Every insertion and search operation in a BST relies on the fundamental ordering property that governs node placement.
• Insertion Logic — Inserting a new node into a BST follows a recursive or iterative comparison process that preserves the ordering property.
• JavaScript Implementation of Insertion — In JavaScript, BST insertion can be implemented as a recursive method on the tree class that navigates to the correct position.
• Search Logic — Searching a BST exploits the ordering property to eliminate half of the remaining nodes at each comparison step.
• Best Case Performance — In the best case, both insertion and search operate in O(log n) time when the BST is balanced.
• Worst Case Performance — In the worst case, a BST degrades to O(n) time for insertion and search when the tree becomes skewed or unbalanced.
• Comparing Best and Worst Case Scenarios — Understanding the gap between best and worst case performance helps developers make informed decisions about when and how to use BSTs.

Deletion Operations

• Overview of BST Deletion Cases — Deleting a node from a Binary Search Tree requires handling three distinct cases depending on the structure of the node being removed.
• Case 1: Deleting a Leaf Node — A leaf node has no children, making it the simplest case to handle during deletion.
• Case 2: Deleting a Node with One Child — When the node to be deleted has exactly one child, that child takes the place of the deleted node in the tree.
• Case 3: Deleting a Node with Two Children — Deleting a node with two children is the most complex case, requiring a replacement value to maintain BST integrity.
• The In-Order Successor — The in-order successor of a node is the smallest node in its right subtree, and it is the most commonly used replacement when deleting a node with two children.
• The In-Order Predecessor — The in-order predecessor is the largest node in the left subtree and serves as an alternative replacement node during deletion.
• Preserving BST Integrity After Deletion — Regardless of which case applies, the fundamental goal of deletion is to ensure the BST property holds for every node in the tree after the operation.

Tree Traversal Strategies

• In-Order Traversal (Left → Root → Right) — In-order traversal visits the left subtree first, then the root node, and finally the right subtree, producing nodes in ascending sorted order for a binary search tree.
• Pre-Order Traversal (Root → Left → Right) — Pre-order traversal visits the root node first, then recursively traverses the left subtree, followed by the right subtree.
• Post-Order Traversal (Left → Right → Root) — Post-order traversal recursively visits the left subtree and right subtree before processing the root node, ensuring children are always handled before their parent.
• Recursive vs. Iterative Traversal Implementations — All three traversal strategies can be implemented either recursively using the call stack or iteratively using an explicit stack data structure.
• Practical Use Cases for Each Traversal — Each traversal strategy is suited to specific real-world tasks, and selecting the correct one is critical to solving tree-based problems efficiently.
• Traversal and Tree Serialization — Tree serialization is the process of converting a tree structure into a linear sequence of values that can be stored or transmitted and later reconstructed.

Implementing a BST in JavaScript

• Defining the Node Class — Every BST is built from individual nodes, each storing a value and references to its left and right children. In JavaScript, a Node class provides the blueprint for these building blocks.
• Setting Up the BinarySearchTree Class — The BST itself is represented as a class that tracks the root node and exposes methods for insertion, deletion, and traversal.
• Implementing the Insert Method — The insert method adds a new value to the correct position in the BST by comparing the new value against existing nodes and traversing left or right accordingly.
• Implementing Search / Lookup — A search method traverses the BST to determine whether a given value exists, exploiting the ordered property to eliminate half the remaining tree at each step.
• Implementing BST Traversal Methods — Traversal methods — in-order, pre-order, and post-order — are implemented as recursive functions that visit nodes in a specific sequence and collect or process their values.
• Implementing the Delete Method — Deletion is the most complex BST operation because removing a node must preserve the BST ordering property, with different logic required depending on whether the node has zero, one, or two children.
• Putting It All Together: Testing the BST — After implementing the Node and BinarySearchTree classes with insert, delete, search, and traversal methods, testing with concrete examples validates the implementation and reinforces understanding.

Student Learning Outcomes

By the end of this module, students will be able to:

Course Outcomes (reference)