Binary Search Trees & Huffman Coding – Key Vocabulary

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/28

flashcard set

Earn XP

Description and Tags

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

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

29 Terms

1
New cards

Binary Tree

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

2
New cards

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.

3
New cards

Root

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

4
New cards

Subtree

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

5
New cards

Path Length

The number of edges along a path between two nodes.

6
New cards

Node Depth

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

7
New cards

Level

All nodes that share the same depth in a tree.

8
New cards

Sibling Nodes

Nodes that share the same parent.

9
New cards

Left Child

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

10
New cards

Right Child

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

11
New cards

Leaf (External Node)

A node with no children.

12
New cards

Tree Height

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

13
New cards

Traversal

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

14
New cards

Inorder Traversal

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

15
New cards

Preorder Traversal

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

16
New cards

Postorder Traversal

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

17
New cards

Depth-First Traversal

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

18
New cards

Breadth-First Traversal

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

19
New cards

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.

20
New cards

BST Deletion

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

21
New cards

Deletion Case 1 (No Left Child)

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

22
New cards

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.

23
New cards

Rightmost Node

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

24
New cards

MVC Architecture (for BST Visualization)

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

25
New cards

Huffman Coding

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

26
New cards

Huffman Tree

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

27
New cards

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.

28
New cards

ASCII Limitation

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

29
New cards

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.