Binary Search Trees & Huffman Coding – Key Vocabulary

Vocabulary flashcards covering core terminology about binary search trees, their operations, tree traversal, and Huffman coding with related greedy algorithms.

Binary Tree

Hierarchical data structure that is either empty or contains a root and up to two subtrees (left and right).

Binary Search Tree (BST)

A binary tree in which left child < parent and right child > parent, with no duplicate values, enabling O(log n) search, insert, and delete operations in average cases.

Root

The top‐most node of a tree; the ancestor of all other nodes.

Subtree

A tree formed by a node and all of its descendants; can be left or right in a binary tree.

Path Length

The number of edges along a path between two nodes.

Node Depth

Length of the path from the root to the node (root depth = 0).

Level

All nodes that share the same depth in a tree.

Sibling Nodes

Nodes that share the same parent.

Left Child

The root of the left subtree of a node; holds a smaller value than its parent in a BST.

Right Child

The root of the right subtree of a node; holds a larger value than its parent in a BST.

Leaf (External Node)

A node with no children.

Tree Height

Length of the longest path from the root to any leaf; 0 for a single‐node tree, –1 for an empty tree.

Traversal

Systematic process of visiting every node in a tree exactly once.

Inorder Traversal

Visits nodes in the sequence left → root → right; yields ascending order in a BST.

Preorder Traversal

Visits nodes in the sequence root → left → right; useful for copying a tree.

Postorder Traversal

Visits nodes in the sequence left → right → root; useful for deleting/freeing nodes.

Depth-First Traversal

Traversal that explores as far along each branch as possible (preorder, inorder, postorder variations).

Breadth-First Traversal

Traversal that visits nodes level by level from the root downward (also called level-order).

BST Insertion

Operation that places a new key by traversing from the root to a leaf, linking it as a left child if smaller, right child if larger.

BST Deletion

Operation that removes a node while preserving BST properties; handled by cases based on the node’s children.

Deletion Case 1 (No Left Child)

If the node has no left child, link its parent directly to its right child.

Deletion Case 2 (Has Left Child)

If the node has a left child, replace its value with the rightmost node in its left subtree, then delete that rightmost node.

Rightmost Node

The node with the greatest key in a subtree (furthest right along right children).

MVC Architecture (for BST Visualization)

Software pattern where the Model stores tree data, the View renders the tree, and the Controller handles user interaction.

Huffman Coding

Compression technique that assigns shorter binary codes to more frequent characters by building a frequency-based binary (Huffman) tree.

Huffman Tree

Binary tree where characters are leaves and edge directions (left = 0, right = 1) define prefix-free codes used for compression.

Decoding (Huffman)

Process of reading bits from the root, moving left on 0 and right on 1 until a leaf is reached to retrieve each character.

ASCII Limitation

Standard fixed-length coding where every character uses 8 bits, regardless of frequency, leading to larger file sizes than Huffman coding.

Greedy Algorithm

Algorithmic approach that makes the locally optimal choice at each step, e.g., Huffman coding or U.S. coin change; may not always yield global optimum.