PadhaikoAll subjects

Definition and tree terminologies · Binary trees · Binary search tree

Data Structure and Algorithms (ENCT 252)

Open in the Padhaiko app

5.1 Definition and tree terminologies

Definition

Tree Data Structure

A tree is a non-linear, hierarchical collection of one or more nodes such that:

  1. There exists a distinguished node designated as the root.
  2. 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.

Conceptual Hierarchy of a TreeText
                       [ Root (A) ]           <-- Level 0
                       /          \
               [ Child (B) ]    [ Child (C) ] <-- Level 1
                /         \           \
            [ D ]        [ E ]       [ F ]    <-- Level 2 (Leaves)

Tree Terminologies

Comprehensive Tree Terminology Guide
TermFormal DefinitionExample in Diagram Above
RootThe topmost entry node having no incoming parent edgeNode
ParentA node that has direct directed links to successor child nodes is parent of and
ChildA node directly connected to and descended from a parent node and are children of
SiblingsChildren nodes sharing the exact same parent node and are siblings
AncestorAny predecessor node along the path from the root down to that nodeAncestors of are and
DescendantAny node reachable by traversing downward edges from that nodeDescendants 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 NodeThe total number of children emanating from that node
Degree of a TreeThe maximum degree among all nodes in the treeTree degree is
Path & LengthA sequence of contiguous edges; length is the number of edgesPath has length
Level of a NodeDistance from root in edges (root at level 0; or 1 by some conventions)Level of is ; level of is
Depth of a NodeNumber of edges along the unique path from root to that node
Height of a NodeNumber of edges on the longest downward path from node to a leaf
Height of a TreeThe height of the root node (maximum level among all nodes)Tree height is

5.2 Binary trees

5.2.1 Definition and types

Definition

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

  1. 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 .
  2. 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.
  3. 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 .
  4. Balanced Binary Tree:
    • For every node, the height difference between its left and right subtrees (the balance factor) is at most .
  5. 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.
Essential Mathematical Properties of Binary Trees
Property MetricMathematical 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 NodesIn 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.

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;

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 ().

The Three Standard Depth-First Binary Tree Traversals
Traversal TypeVisiting SequenceRecursive StrategyPrimary Algorithmic Application
Pre-order1. Visit Root
2. Traverse Left Subtree
3. Traverse Right Subtree
Copying/cloning trees, serialization, prefix expression generation
In-order1. Traverse Left Subtree
2. Visit Root
3. Traverse Right Subtree
Generates keys in strictly ascending sorted order for BST
Post-order1. Traverse Left Subtree
2. Traverse Right Subtree
3. Visit Root
Bottom-up deletion/freeing of nodes, postfix expression evaluation
Recursive Traversal Algorithms in CC
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

Definition

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

  1. Prefix Rule: No encoded character bit-string is a prefix of another encoded character bit-string (e.g., if A is 01, no other character can begin with 01). This guarantees unambiguous instant decodability without delimiters.
  2. 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

  1. Count the frequency of each unique character in the message.
  2. Create a leaf node for each character and insert all nodes into a min-priority queue keyed on frequency.
  3. 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.
  4. The sole remaining node in the queue is the root of the full binary Huffman tree.
  5. 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

Definition

Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree in which every node satisfies the binary search property:

  1. All keys stored in the left subtree of are strictly less than : .
  2. All keys stored in the right subtree of are strictly greater than : .
  3. Both left and right subtrees must themselves be valid binary search trees.

Fundamental BST Operations

  1. 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.
  2. Insertion: Traverse downward using the search logic until reaching a NULL link, then attach a new node.
  3. 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:

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:

BST Insertion and Search Implementation in CC
#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


Worked Examples

Example 1

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: visit B, visit D, traverse right child E, visit E, visit G. Left subtree order: B, D, E, G.
  • Traverse right subtree rooted at C: visit C, traverse right child F, visit F, visit H, visit I. 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. Visit D.
    • Visit B.
    • Right of B: E, which has left child G. Visit G, then E.
    • Left subtree yields: D B G E.
  • Visit root A.
  • Right subtree of A:
    • C has no left child; visit C.
    • Right of C is F: left of F is H, visit H, visit F, right of F is I, visit I.
    • 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.
Answer:
  • 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
Example 2

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:

  1. Insert 45: Root.
  2. Insert 15: left child of 45.
  3. Insert 79: right child of 45.
  4. Insert 90: right child of 79.
  5. Insert 10: left child of 15.
  6. Insert 55: left child of 79.
  7. Insert 12: right child of 10.
  8. Insert 20: right child of 15.
  9. Insert 50: left child of 55.
               45
             /    \
           15      79
          /  \    /  \
        10   20  55   90
         \       /
         12     50

Tracing 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 is 20 (which has no left child), so in-order successor is 20.
  • Replace value 15 with 20.
  • Delete original node 20 from the right subtree (a leaf node).
Answer:

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.

Example 3

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].

  1. Extract two minimums: A: 3 and O: 5. Create internal node N1 with frequency . Assign left child = A: 3 (), right child = O: 5 (). Queue becomes: [T: 7, N1: 8, E: 10].
  2. Extract two minimums: T: 7 and N1: 8. Create internal node N2 with frequency . Assign left child = T: 7 (), right child = N1: 8 (). Queue becomes: [E: 10, N2: 15].
  3. Extract two minimums: E: 10 and N2: 15. Create root node R with frequency . Assign left child = E: 10 (), right child = N2: 15 ().

Tree is complete.

Assigning Huffman Codes and Total Bit Calculation:

  • E: path 0 (length 1)
  • T: path 10 (length 2)
  • A: path 110 (length 3)
  • O: path 111 (length 3)

Total weighted bit length:

Fixed-length 2-bit code ( bits/char):

Answer:
  • 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).
Example 4

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:

  1. The left and right children of node B
  2. 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:

  1. Node B is stored at index :
    • Left child index: D.
    • Right child index: E.
  2. Node F is stored at index :
    • Parent index: C.
Answer:

In the 0-based array [A, B, C, D, E, F, G]:

  • Left child of B is D (index 3), and right child of B is E (index 4).
  • Parent of F is C (index 2).

Exercises

Exercise Questions: Trees and BST

Question 1

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:

  1. In any tree, every node except the root has exactly one incoming edge. Thus, the total number of edges is:
  1. Each internal node has degree 2, contributing 2 downward outgoing edges. Leaves contribute 0 outgoing edges:

Equating both expressions for :

Substitute :

Answer:

In any strictly binary tree, the total number of edges is . Substituting yields , which simplifies directly to .

Question 2

Reconstruct the unique binary tree given the following traversal sequences:

Determine its Post-order traversal sequence.

Step-by-Step Tree Reconstruction:

  1. The first node in Pre-order is the root: A.
  2. Locate A in the In-order sequence D B E A F C:
    • Left subtree in-order: D B E (3 nodes)
    • Right subtree in-order: F C (2 nodes)
  3. Corresponding subtrees in Pre-order:
    • Left subtree pre-order: B D E (first node B is left child of A)
    • Right subtree pre-order: C F (first node C is right child of A)
  4. Reconstruct left subtree rooted at B:
    • In-order: D B E D is left child of B, E is right child of B.
  5. Reconstruct right subtree rooted at C:
    • In-order: F C F is left child of C (no right child).

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.

Answer:

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.

Question 3

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 35

Deleting 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 from 70: node 60. Node 60 has no left child, so in-order successor is 60.
  • Copy value 60 into the root position.
  • Delete original node 60 from right subtree (it has no children, so simply detach it).
Answer:

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).

Question 4

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].

  1. Combine D: 3 and E: 4 (left: D, right: E). Queue: [N_1: 7, A: 10, C: 12, F: 13, B: 15].
  2. Combine N_1: 7 and A: 10 (left: , right: A). Queue: [C: 12, F: 13, B: 15, N_2: 17].
  3. Combine C: 12 and F: 13 (left: C, right: F). Queue: [B: 15, N_2: 17, N_3: 25].
  4. Combine B: 15 and N_2: 17 (left: B, right: ). Queue: [N_3: 25, N_4: 32].
  5. Combine N_3: 25 and N_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.

Answer:
  • Huffman Codes: C: 00, F: 01, B: 10, A: 111, D: 1100, E: 1101
  • Total encoded message length: bits.
Question 5

Write recursive C functions to:

  1. Print the in-order traversal of a binary tree
  2. 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:

In-order Traversal and BST Search in CC
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 .
Answer:

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.

Question 6

For a perfect binary tree of height (where the root node is at height ):

  1. Compute the maximum number of nodes in the entire tree.
  2. Compute the number of leaf nodes.
  3. Verify the relationship between leaf nodes and degree-2 internal nodes.

Formulas and Calculations: For height (levels ):

  1. Total number of nodes :
  1. Number of leaf nodes at level :
  1. Number of internal nodes :

Checking the relationship :

The relation holds with exact equality.

Answer:
  1. Maximum total nodes: .
  2. Number of leaf nodes: .
  3. Internal nodes , verifying ().

Past exam questions for Data Structure and Algorithms

← Linked ListBalanced binary tree · Introduction to red-black tree · B-Tree: Need… →