Definition and tree terminologies · Binary trees · Binary search tree
Open in the Padhaiko app5.1 Definition and tree terminologies
Tree Data Structure
A tree is a non-linear, hierarchical collection of one or more nodes such that:
- There exists a distinguished node designated as the root.
- The remaining nodes are partitioned into disjoint non-empty sets , each of which is itself a tree, called a subtree of the root.
A tree contains no closed loops (cycles) and is connected by exactly edges for nodes.
[ Root (A) ] <-- Level 0
/ \
[ Child (B) ] [ Child (C) ] <-- Level 1
/ \ \
[ D ] [ E ] [ F ] <-- Level 2 (Leaves)Tree Terminologies
| Term | Formal Definition | Example in Diagram Above |
|---|---|---|
| Root | The topmost entry node having no incoming parent edge | Node |
| Parent | A node that has direct directed links to successor child nodes | is parent of and |
| Child | A node directly connected to and descended from a parent node | and are children of |
| Siblings | Children nodes sharing the exact same parent node | and are siblings |
| Ancestor | Any predecessor node along the path from the root down to that node | Ancestors of are and |
| Descendant | Any node reachable by traversing downward edges from that node | Descendants of are |
| Leaf (Terminal) | A node having degree zero (no children) | Nodes |
| Internal (Non-terminal) | Any node possessing at least one child (non-leaf) | Nodes |
| Degree of a Node | The total number of children emanating from that node | |
| Degree of a Tree | The maximum degree among all nodes in the tree | Tree degree is |
| Path & Length | A sequence of contiguous edges; length is the number of edges | Path has length |
| Level of a Node | Distance from root in edges (root at level 0; or 1 by some conventions) | Level of is ; level of is |
| Depth of a Node | Number of edges along the unique path from root to that node | |
| Height of a Node | Number of edges on the longest downward path from node to a leaf | |
| Height of a Tree | The height of the root node (maximum level among all nodes) | Tree height is |
5.2 Binary trees
5.2.1 Definition and types
Binary Tree
A binary tree is a finite set of zero or more nodes such that either it is empty, or it consists of a root node and two disjoint binary trees called the left subtree and the right subtree. Every node in a binary tree has a maximum degree of .
Primary Classifications of Binary Trees
- Strictly Binary Tree (Full / Proper Binary Tree):
- Every node has either or children. No node has exactly 1 child.
- If a strictly binary tree has leaves and internal nodes, then .
- Complete Binary Tree:
- All levels are completely filled except possibly the last level.
- All nodes in the last level are packed as far left as possible without any empty intervening gaps.
- Perfect Binary Tree:
- All internal nodes have exactly 2 children, and all leaf nodes reside at the exact same depth/level.
- For a perfect binary tree of height (root at height 0), the total number of nodes is , and the number of leaf nodes is .
- Balanced Binary Tree:
- For every node, the height difference between its left and right subtrees (the balance factor) is at most .
- Degenerate (Skewed) Binary Tree:
- Every internal parent node possesses only a single child. The tree structurally degenerates into a linear linked list with height , losing logarithmic efficiency.
| Property Metric | Mathematical Formulation (Root at Level / Height ) |
|---|---|
| Max nodes at level | nodes |
| Max nodes in tree of height | |
| Min nodes in tree of height | nodes (Skewed tree) |
| Min height for nodes | |
| Max height for nodes | |
| Leaves vs Degree-2 Nodes | In any binary tree: |
5.2.2 Array and linked list representation
1. Sequential (Array) Representation
In an array representation, nodes are mapped to array indices based on level-order traversal. For a complete binary tree, this uses memory with zero pointer overhead.
- 0-Based Indexing:
- Root node is placed at index
0. - For a node stored at index :
- Left child:
2*i + 1 - Right child:
2*i + 2 - Parent:
(i - 1) / 2(integer division)
- Left child:
- Root node is placed at index
- 1-Based Indexing:
- Root node is placed at index
1. - For a node stored at index :
- Left child:
2*i - Right child:
2*i + 1 - Parent:
i / 2
- Left child:
- Root node is placed at index
Limitation: While ideal for complete trees, skewed trees waste massive amounts of array storage on empty intermediate indices ( slots required for only nodes).
2. Linked List (Node Pointer) Representation
Each node is dynamically allocated in heap memory and maintains two pointer fields:
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
- If a child does not exist, the corresponding pointer is set to
NULL. - Linked representation dynamically adapts to arbitrary tree topologies without wasting contiguous memory blocks.
5.2.3 Traversal algorithms: Pre-order, in-order and post-order traversal
Tree traversal is the algorithmic process of visiting every node in the tree structure exactly once. Binary tree depth-first traversals are defined recursively based on the relative position of the Root node (), Left subtree (), and Right subtree ().
| Traversal Type | Visiting Sequence | Recursive Strategy | Primary Algorithmic Application |
|---|---|---|---|
| Pre-order | 1. Visit Root 2. Traverse Left Subtree 3. Traverse Right Subtree | Copying/cloning trees, serialization, prefix expression generation | |
| In-order | 1. Traverse Left Subtree 2. Visit Root 3. Traverse Right Subtree | Generates keys in strictly ascending sorted order for BST | |
| Post-order | 1. Traverse Left Subtree 2. Traverse Right Subtree 3. Visit Root | Bottom-up deletion/freeing of nodes, postfix expression evaluation |
void preorder(TreeNode *root) {
if (root != NULL) {
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
}
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
void postorder(TreeNode *root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
}5.2.4 Application of full binary tree: Huffman algorithm
Huffman Coding
Huffman coding is an entropy-based, lossless data compression algorithm. It constructs a full binary tree (where every non-leaf node has exactly two children) by iteratively combining the lowest-frequency character nodes using a greedy min-priority queue, assigning shorter bit codes to frequent characters and longer codes to rarer characters.
Properties of Huffman Codes
- Prefix Rule: No encoded character bit-string is a prefix of another encoded character bit-string (e.g., if
Ais01, no other character can begin with01). This guarantees unambiguous instant decodability without delimiters. - Optimal Prefix Code: Huffman coding minimizes the weighted average code length:
where is character probability/frequency and is code length in bits.
Greedy Huffman Tree Construction Algorithm
- Count the frequency of each unique character in the message.
- Create a leaf node for each character and insert all nodes into a min-priority queue keyed on frequency.
- While priority queue size :
- Extract the two nodes with the lowest frequencies: and .
- Create a new internal parent node with frequency .
- Assign as left child () and as right child () of .
- Insert back into the min-priority queue.
- The sole remaining node in the queue is the root of the full binary Huffman tree.
- Traverse from root to leaves to assign variable-length binary codes.
5.3 Binary search tree
5.3.1 Definition and operations on binary search tree: Insertion, deletion, searching and traversing
Binary Search Tree (BST)
A Binary Search Tree (BST) is a binary tree in which every node satisfies the binary search property:
- All keys stored in the left subtree of are strictly less than : .
- All keys stored in the right subtree of are strictly greater than : .
- Both left and right subtrees must themselves be valid binary search trees.
Fundamental BST Operations
- Searching: Compare search key with :
- If , search succeeds ().
- If , recurse into left subtree.
- If , recurse into right subtree.
- If pointer becomes
NULL, key does not exist.
- Insertion: Traverse downward using the search logic until reaching a
NULLlink, then attach a new node. - Traversing: An In-order traversal () of a BST always visits nodes in strictly increasing (sorted) numerical order.
Deletion in BST (Three Cases)
When deleting a target node from a BST:
- Case 1: is a leaf node (0 children): Simply remove and set its parent's corresponding child pointer to
NULL. Free . - Case 2: has exactly one child: Bypass by connecting 's parent directly to 's single child. Free .
- Case 3: has two children:
- Find 's in-order successor (the minimum key in 's right subtree, found by going right once, then left as far as possible). Alternatively, use the in-order predecessor (maximum key in left subtree).
- Copy the key and data of into node .
- Recursively delete node from 's right subtree (since is the minimum in that subtree, it has at most one child—a right child).
5.3.2 Construction of binary search tree
Constructing a BST from an input sequence involves repeatedly inserting each element into the tree starting from an initially empty root:
#include <stdio.h>
#include <stdlib.h>
typedef struct BSTNode {
int key;
struct BSTNode *left;
struct BSTNode *right;
} BSTNode;
BSTNode* createBSTNode(int val) {
BSTNode *node = (BSTNode *)malloc(sizeof(BSTNode));
node->key = val;
node->left = node->right = NULL;
return node;
}
BSTNode* insertBST(BSTNode *root, int val) {
if (root == NULL) {
return createBSTNode(val);
}
if (val < root->key) {
root->left = insertBST(root->left, val);
} else if (val > root->key) {
root->right = insertBST(root->right, val);
}
return root;
}
BSTNode* searchBST(BSTNode *root, int target) {
if (root == NULL || root->key == target) {
return root;
}
if (target < root->key) {
return searchBST(root->left, target);
}
return searchBST(root->right, target);
}Operational Complexity of BST
- Average Case (Random Keys, Balanced): Search, insertion, and deletion take time, where tree height .
- Worst Case (Sorted Keys, Skewed Tree): Search, insertion, and deletion degrade to time because the tree degenerates into a linear list of height .
Worked Examples
1
Given the binary tree below:
A
/ \
B C
/ \ \
D E F
/ / \
G H I
Determine the Pre-order, In-order, and Post-order traversals.
Evaluating Pre-order Traversal ():
- Visit root
A. - Traverse left subtree rooted at
B: visitB, visitD, traverse right childE, visitE, visitG. Left subtree order:B, D, E, G. - Traverse right subtree rooted at
C: visitC, traverse right childF, visitF, visitH, visitI. Right subtree order:C, F, H, I. - Combined Pre-order:
A B D E G C F H I.
Evaluating In-order Traversal ():
- Left subtree of
A:- Left of
B:D. VisitD. - Visit
B. - Right of
B:E, which has left childG. VisitG, thenE. - Left subtree yields:
D B G E.
- Left of
- Visit root
A. - Right subtree of
A:Chas no left child; visitC.- Right of
CisF: left ofFisH, visitH, visitF, right ofFisI, visitI. - Right subtree yields:
C H F I.
- Combined In-order:
D B G E A C H F I.
Evaluating Post-order Traversal ():
- Process left subtree of
A:D G E B. - Process right subtree of
A:H I F C. - Visit root
A. - Combined Post-order:
D G E B H I F C A.
- Pre-order ():
A B D E G C F H I - In-order ():
D B G E A C H F I - Post-order ():
D G E B H I F C A
2
Construct a Binary Search Tree (BST) by sequentially inserting keys: 45, 15, 79, 90, 10, 55, 12, 20, 50. Then trace the deletion of node 15 (a node with two children) using its in-order successor.
Sequential Insertion Trace:
- Insert
45: Root. - Insert
15: left child of45. - Insert
79: right child of45. - Insert
90: right child of79. - Insert
10: left child of15. - Insert
55: left child of79. - Insert
12: right child of10. - Insert
20: right child of15. - Insert
50: left child of55.
45
/ \
15 79
/ \ / \
10 20 55 90
\ /
12 50Tracing Deletion of Node 15 (Two Children Case): Node 15 has two subtrees: left subtree rooted at 10 and right subtree rooted at 20.
- Locate in-order successor: minimum value in right subtree of
15. Right child is20(which has no left child), so in-order successor is20. - Replace value
15with20. - Delete original node
20from the right subtree (a leaf node).
Resulting BST after deleting 15:
45
/ \
20 79
/ / \
10 55 90
\ /
12 50
In-order traversal confirms correct ordering: 10, 12, 20, 45, 50, 55, 79, 90.
3
Construct a Huffman Tree for the characters with given frequencies: E: 10, T: 7, O: 5, A: 3. Determine the Huffman binary code for each character, calculate the total encoded bit length, and compare it with a fixed 2-bit encoding.
Building the Huffman Tree via Min-Priority Queue: Initial sorted queue: [A: 3, O: 5, T: 7, E: 10].
- Extract two minimums:
A: 3andO: 5. Create internal nodeN1with frequency . Assign left child =A: 3(), right child =O: 5(). Queue becomes:[T: 7, N1: 8, E: 10]. - Extract two minimums:
T: 7andN1: 8. Create internal nodeN2with frequency . Assign left child =T: 7(), right child =N1: 8(). Queue becomes:[E: 10, N2: 15]. - Extract two minimums:
E: 10andN2: 15. Create root nodeRwith frequency . Assign left child =E: 10(), right child =N2: 15().
Tree is complete.
Assigning Huffman Codes and Total Bit Calculation:
E: path0(length 1)T: path10(length 2)A: path110(length 3)O: path111(length 3)
Total weighted bit length:
Fixed-length 2-bit code ( bits/char):
- Codes:
E: 0,T: 10,A: 110,O: 111 - Total bit length: bits (saving 2 bits compared to 50 bits under fixed-length encoding, and saving 152 bits compared to 8-bit ASCII).
4
A complete binary tree contains 7 nodes labeled in level-order as: [A, B, C, D, E, F, G]. Map this tree into a 0-based array and calculate:
- The left and right children of node
B - The parent of node
F
Mapping Nodes to Array Indices: Level-order sequential placement:
Tree[0] = A(Root)Tree[1] = B,Tree[2] = C(Level 1)Tree[3] = D,Tree[4] = E,Tree[5] = F,Tree[6] = G(Level 2)
Index Calculations:
- Node
Bis stored at index :- Left child index:
D. - Right child index:
E.
- Left child index:
- Node
Fis stored at index :- Parent index:
C.
- Parent index:
In the 0-based array [A, B, C, D, E, F, G]:
- Left child of
BisD(index 3), and right child ofBisE(index 4). - Parent of
FisC(index 2).
Exercises
Exercise Questions: Trees and BST
Prove mathematically that in any non-empty strictly binary tree (full binary tree), the number of leaf nodes is given by , where is the number of internal nodes with degree 2.
Expressing Total Nodes and Edges: Let be the total number of nodes in the strictly binary tree. Because every node has either 0 or 2 children, there are no nodes with 1 child ().
Counting Total Edges:
- In any tree, every node except the root has exactly one incoming edge. Thus, the total number of edges is:
- Each internal node has degree 2, contributing 2 downward outgoing edges. Leaves contribute 0 outgoing edges:
Equating both expressions for :
Substitute :
In any strictly binary tree, the total number of edges is . Substituting yields , which simplifies directly to .
Reconstruct the unique binary tree given the following traversal sequences:
- In-order:
D B E A F C - Pre-order:
A B D E C F
Determine its Post-order traversal sequence.
Step-by-Step Tree Reconstruction:
- The first node in Pre-order is the root:
A. - Locate
Ain the In-order sequenceD B E A F C:- Left subtree in-order:
D B E(3 nodes) - Right subtree in-order:
F C(2 nodes)
- Left subtree in-order:
- Corresponding subtrees in Pre-order:
- Left subtree pre-order:
B D E(first nodeBis left child ofA) - Right subtree pre-order:
C F(first nodeCis right child ofA)
- Left subtree pre-order:
- Reconstruct left subtree rooted at
B:- In-order:
D B EDis left child ofB,Eis right child ofB.
- In-order:
- Reconstruct right subtree rooted at
C:- In-order:
F CFis left child ofC(no right child).
- In-order:
Constructed Binary Tree Structure:
A
/ \
B C
/ \ /
D E F
Post-order traversal ():
- Left subtree of
A:D E B - Right subtree of
A:F C - Root:
A
Sequence: D E B F C A.
The reconstructed binary tree has root A, left child B (with children D, E), and right child C (with left child F). Its Post-order traversal is D E B F C A.
Construct a Binary Search Tree (BST) by inserting the sequence: 50, 30, 70, 20, 40, 60, 80, 10, 25, 35. Trace the deletion of the root node 50 using its in-order successor.
Constructing the Initial BST:
- Root:
50 30 < 50(left of 50);70 > 50(right of 50)20 < 30(left of 30);40 > 30(right of 30)60 < 70(left of 70);80 > 70(right of 70)10 < 20(left of 20);25 > 20(right of 20)35 < 40(left of 40)
50
/ \
30 70
/ \ / \
20 40 60 80
/ \ /
10 25 35Deleting Root Node 50: Node 50 has two children (30 and 70).
- Find in-order successor: minimum key in right subtree (rooted at
70). Go left from70: node60. Node60has no left child, so in-order successor is60. - Copy value
60into the root position. - Delete original node
60from right subtree (it has no children, so simply detach it).
After deleting node 50, the new root is 60, and the tree is:
60
/ \
30 70
/ \ \
20 40 80
/ \ /
10 25 35
In-order verification: 10, 20, 25, 30, 35, 40, 60, 70, 80 (strictly sorted).
Construct the Huffman tree for the characters with frequencies: D: 3, E: 4, A: 10, C: 12, F: 13, B: 15. Determine the code word for each character and calculate the total number of bits required to encode the entire message.
Greedy Huffman Tree Construction: Sorted queue: [D: 3, E: 4, A: 10, C: 12, F: 13, B: 15].
- Combine
D: 3andE: 4(left: D, right: E). Queue:[N_1: 7, A: 10, C: 12, F: 13, B: 15]. - Combine
N_1: 7andA: 10(left: , right: A). Queue:[C: 12, F: 13, B: 15, N_2: 17]. - Combine
C: 12andF: 13(left: C, right: F). Queue:[B: 15, N_2: 17, N_3: 25]. - Combine
B: 15andN_2: 17(left: B, right: ). Queue:[N_3: 25, N_4: 32]. - Combine
N_3: 25andN_4: 32(left: , right: ).
Assigning Codes and Calculating Total Length: Left edge = 0, Right edge = 1:
C:00(length 2)F:01(length 2)B:10(length 2)A:111(length 3)D:1100(length 4)E:1101(length 4)
Total bit length:
Wait: let us check the path to in : has left child () and right child (). Path to from root: length 3. If assigned left child and right child , length is still 3. bits.
- Huffman Codes:
C: 00,F: 01,B: 10,A: 111,D: 1100,E: 1101 - Total encoded message length: bits.
Write recursive C functions to:
- Print the in-order traversal of a binary tree
- Search for a key in a Binary Search Tree
Explain the worst-case and average-case time complexity of the search function.
C Code Implementation:
typedef struct TreeNode {
int key;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void inorder(TreeNode *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->key);
inorder(root->right);
}
}
TreeNode* searchBST(TreeNode *root, int target) {
if (root == NULL || root->key == target) {
return root;
}
if (target < root->key) {
return searchBST(root->left, target);
}
return searchBST(root->right, target);
}Complexity Analysis:
- Average-case time complexity: when keys are randomly inserted and the tree maintains balanced height .
- Worst-case time complexity: when keys are inserted in strictly sorted or reverse-sorted order, causing the tree to degenerate into a skewed chain of height .
The recursive searchBST compares target with root->key, recursing left if smaller and right if larger. It achieves average-case time complexity and worst-case time complexity on skewed trees.
For a perfect binary tree of height (where the root node is at height ):
- Compute the maximum number of nodes in the entire tree.
- Compute the number of leaf nodes.
- Verify the relationship between leaf nodes and degree-2 internal nodes.
Formulas and Calculations: For height (levels ):
- Total number of nodes :
- Number of leaf nodes at level :
- Number of internal nodes :
Checking the relationship :
The relation holds with exact equality.
- Maximum total nodes: .
- Number of leaf nodes: .
- Internal nodes , verifying ().