Implementation and Analysis of Tree

Assignment Goals

The original question number 1 is written in hand-written-technical-report. This report deals only with programming assignments.

  1. Implement the function that finds a successor of node in the inorder traversal.
  2. Implement the function that finds a predecessor of node in the inorder traversal.
  3. In the code provided in the page 60 and 61, the case 3 was implemented using the successor at the right subtree. Revise this part by using the predecessor at the left subtree. Verify your code by running the following three examples. Namely, the revised code should produces the same results of the original code. Refer to the attached original code (‘bst_insertion_deletion.cpp’).

#1. Introduction(Theoretical Background, Logic)

A tree is a hierarchical data structure consisting of nodes connected by edges, unlike linear structures such as lists or stacks. Each node (except the root) has exactly one parent and may have multiple children.

Key Terms:

  • Root: Topmost node without a parent
  • Leaf (terminal node): Node with no children
  • Internal node: Node with at least one child
  • Level: Layer number of a node
  • Height: Maximum level in the tree
  • Degree: Number of child nodes

Binary Tree

A binary tree allows each node to have at most two children — left and right.
If a tree has N nodes, it has N − 1 links.
The height satisfies: $\lceil \log_2 (n + 1) \rceil \le h \le n$

Full Binary Tree: All levels completely filled. $\sum_{i=0}^{k-1} 2^i = 2^k - 1$
Complete Binary Tree: All levels filled except possibly the last, filled from left to right.

Implementation

  • Array: Simple but wasteful if not full/complete.
    • Parent: $i/2$, Left: 2i, Right: 2i+1
  • Linked List: Each node contains data, left, and right pointers.

Traversal

  • Preorder: V → L → R
  • Inorder: L → V → R
  • Postorder: L → R → V
  • Level-order: Visit nodes level by level using a queue.

Additional Concepts

  • Predecessor: Largest value in the left subtree (= the rightmost node in the left subtree)
  • Successor: Smallest value in the right subtree (= the leftmost node in the left subtree)
  • Threaded Binary Tree: Enables non-recursive traversal by linking nodes through unused pointers.

#2. Problem Definition

In this assignment, three different implementations are required:

1. Implement the function that finds a successor of node in the inorder traversal.

– Refer to the following pseudo code.

– Use the given data structure and simple binary tree example in p3.

더보기

OUTPUT :

A
C

B

G

D

F

E

 Tree_successor(x)
 {
     if x->right != NULL //x’s right subtree is not null
         return the leftmost node of right subtree

     //x’s right subtree is null
     y = x->parent
     while (y != NULL and x == y->right) {
         x = y;
         y = y->parent;
     }
     return y;
}
typedef struct TreeNode {
     int data;
     struct TreeNode *left, *right, *parent;
 } TreeNode;
 //      G
//     C       F
//  A  B    D   E
 TreeNode n1 = { 'A', NULL, NULL, NULL };
 TreeNode n2 = { 'B', NULL, NULL, NULL };
 TreeNode n3 = { 'C', &n1, &n2, NULL };
 TreeNode n4 = { 'D', NULL, NULL, NULL };
 TreeNode n5 = { 'E', NULL, NULL, NULL };
 TreeNode n6 = { 'F', &n4, &n5, NULL };
 TreeNode n7 = { 'G', &n3, &n6, NULL };
 TreeNode *exp = &n7;
 TreeNode *tree_successor(TreeNode *p) {
 .....
 }
 void main()
 {
     TreeNode *q = exp;
     n1.parent = &n3;
     n2.parent = &n3;
     n3.parent = &n7;
     n4.parent = &n6;
     n5.parent = &n6;
     n6.parent = &n7;
     n7.parent = NULL;
     // Go to the rightmost node
     ...
     do
     {
     printf("%c\n", q->data); // Output data
     // Call the successor
     q = tree_successor(q);
     } while (q);    // If not null
 }

2. Implement the function that finds a predecessor of node in the inorder traversal.

– Write up the pseudo code by referring to the pseudo code of ‘Tree_successor(x)’.

– Use the given data structure and simple binary tree example in p5.

더보기

Output:

E

F

D

G

B

C

A

typedef struct TreeNode {
     int data;
     struct TreeNode *left, *right, *parent;
 } TreeNode;
 //      G
//     C       F
//  A  B    D   E
 TreeNode n1 = { 'A', NULL, NULL, NULL };
 TreeNode n2 = { 'B', NULL, NULL, NULL };
 TreeNode n3 = { 'C', &n1, &n2, NULL };
 TreeNode n4 = { 'D', NULL, NULL, NULL };
 TreeNode n5 = { 'E', NULL, NULL, NULL };
 TreeNode n6 = { 'F', &n4, &n5, NULL };
 TreeNode n7 = { 'G', &n3, &n6, NULL };
 TreeNode *exp = &n7;
 TreeNode *tree_predecessor(TreeNode *p) {
 .....
 }
 void main()
 {
     TreeNode *q = exp;
     n1.parent = &n3;
     n2.parent = &n3;
     n3.parent = &n7;
     n4.parent = &n6;
     n5.parent = &n6;
     n6.parent = &n7;
     n7.parent = NULL;
     // Go to the rightmost node
     ...
     do
     {
     printf("%c\n", q->data); // Output data
     // Call the predecessor
     q = tree_predecessor(q);
     } while (q);    // If not null
 }

3. In the code provided in the page 60 and 61, the case 3 was implemented using the successor at the right subtree. Revise this part by using the predecessor at the left subtree. Verify your code by running the following three examples. Namely, the revised code should produces the same results of the original code. Refer to the attached original code (‘bst_insertion_deletion.cpp’).

더보기

#3. Algorithm and Data Structure

In this project, the main data structure used is the binary tree, especially the Binary Search Tree (BST).
In a BST, each node’s key satisfies the condition:
$key(left\ subtree) ≤ key(root\ node) ≤ key(right\ subtree)$

Therefore, a BST is very efficient for search operations because the values are stored in ascending order when using inorder traversal.

In the first program, the goal is to implement a function that finds and returns the successor of a given node.
A successor is the smallest node in the right subtree, which can also be described as the leftmost node of the right subtree.

In the second program, the task is to implement a function that finds and returns the predecessor of a given node.
A predecessor is the largest node in the left subtree, which can also be described as the rightmost node of the left subtree.

In the third program, we handle the case where a node to be deleted has two child nodes (both left and right).
In this case, the algorithm uses either the successor or the predecessor to replace the deleted node, ensuring that the BST structure remains correct after deletion.

#4. Implementation Results and Analysis

4.1 Implementation of `tree_successor()` through inorder.

First, let us recall inorder traversal, which follows the order: Left → Node → Right.

The successor of a node is defined as the leftmost node in its right subtree, i.e., the node with the smallest value in the right subtree.

For a given node `x`, `if x->right != NULL`, we move to the right subtree.
Then, to follow the inorder traversal, we keep going down the left child until `y->left == NULL`.
This means we have reached the leftmost node in the right subtree, and we return `y`as the successor.

If the node has no right subtree, we need to look up the tree.
We set `y` as `x->parent`, and then traverse upward while `x` is the right child of `y`.
We continue this until either `y` becomes `NULL`(no successor exists) or `x` becomes the left child of `y`.
Finally, we return `y` as the successor of `x`.

This logic is implemented in the following C function:

더보기

먼저, inorder순서로 순회하는 방식을 다시 상기해보자. inorder이란, L->V->R 순으로 순회하는 방식이다.

successor의 정의는 우측 서브트리에서 가장 좌측에 있는 노드이다. 즉 오른쪽에 있는 서브트리에서 가장 작은 값을 말한다.

따라서 루트가 되는 어떤 노드 `x`에 대해서 우측 서브트리로 가기위해 `x->right != NULL`인 조건을 이용해 우측 서브트리로 이동한다.

이후, inorder 방식의 순회를 이용하기 위해서, `y->left = NULL`일 때 까지 자식노드로 계속해서 내려간다. 이후 `y->left == NULL`인경우 우측 서브트리에서 왼쪽으로 더이상 노드가 없다는 것을 의미하므로 루프를 빠져나와 해당 노드 y를 반환한다.

아래 있는 if문의 경우에는 루트노드의 오른쪽, 서브트리가 존재하지 않는다는 것을 의미하는 상황을 처리해주기 위한 코드이다.

y를 찾는 노드의 부모 노드로 설정해준다. 이후, y가 NULL이 아니고, x(자식노드)가 y(부모)의 오른쪽 노드일 때 계속해서 거슬러 올라간다. y가 NULL일 때 까지(부모노드가 NULL 인 상황), x가 y의 왼쪽 자식이 될 때까지 올라간다. 이후 위에서 successor를 찾고 그 successor, y를 반환한다.

TreeNode * tree_successor(TreeNode *x) {
    TreeNode *y;
    if (x->right != NULL) {
        y = x->right;
        while (y->left) // 중요. 그 다음노드가 null값이 되면안됑~
            y= y->left;
        return y;//go to the leftmost node! starting point
    }
    // x's right subtree is null?
    y = x->parent;
    while (y!=NULL && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

This is a example of case When `y = x-> parent` below is excuted.

this is result! it is same with the given answer

Given OUTPUT :

A
C

B

G

D

F

E

4.2 Implementation of `tree_predecessor()` through inorder.


The predecessor of a node is the largest node in its left subtree, which can also be described as the rightmost node in the left subtree.

Similarly, if a node has a left child, we move to the left subtree and go down to the rightmost node in that subtree. This node is the predecessor.

If the node has no left child, we need to move up the tree.
We traverse upward using the parent pointer until we find a node that is the right child of its parent.
That parent node is then the predecessor of the original node.

TreeNode * tree_predecessor(TreeNode *x) {
    TreeNode *y;
    if (x->left != NULL) { //왼쪽 트리가 있다면,
        y = x->left; // 왼쪽트리가있다면 거기에서 가장 rightmostnode가 predecessor값!
        while (y->right) // 중요. 그 다음노드가 null값이 되면안된다.
            y= y->right;
        return y;//go to the rightmost node! starting point
    }
    // x's left subtree is null?
    y = x->parent;
    while (y!=NULL && x == y->left) {
        x = y;
        y = y->parent;
    }
    return y;
}

it is the result it is same with the given answer

Output:

E

F

D

G

B

C

A

feature / Case Successor Predecessor
Definition Smallest node in right subtree Largest node in left subtree
Also called Leftmost node in right subtree Rightmost node in left subtree
If child subtree exists Move to right child, then go left as far as possible Move to left child, then go right as far as possible
If no child subtree Move up to parent while current node is right child; stop when current node becomes left child Move up to parent while current node is left child; stop when current node becomes right child
Loop termination condition x becomes left child of y or y is NULL x becomes right child of y or y is NULL
Returned node y (successor) y (predecessor)
Example in BST (Inorder) 10 → 15 → 20 → 30; successor of 15 = 20 10 → 15 → 20 → 30; predecessor of 20 = 15

 

The algorithms for finding a successor and a predecessor are very similar and almost symmetric.
Both use the concept of going down a child subtree first (right for successor, left for predecessor) and then moving up the parent chain if necessary.
The key difference is the direction: successor looks for the leftmost node in the right subtree or moves up while coming from a right child, whereas predecessor looks for the rightmost node in the left subtree or moves up while coming from a left child.

4.3 Implementation that deletion of node which has two child nodes using predecessor

In the third program, we handle the case where the node to be deleted has both left and right children.
To maintain the BST structure, the node is replaced with a successor from the right subtree or a predecessor from the left subtree.
The algorithms for successor and predecessor are geometrically symmetric, so reversing the left-right directions allows us to implement either version with the same logic.
The deletion is carried out by copying the replacement node's key into the node to be deleted, and then removing the replacement node, which is guaranteed to have at most one child.
This ensures that the BST property is preserved after deletion.

same as upper problem

// Case 3
else {
    // Find the predecessor at right subtree
    pred_p = t;
    pred = t->left;
    // Keep moving to the right ( rightmost node 찾는다) and find the predecessor
    while (pred->right != NULL) {
       pred_p = pred;
       pred = pred->right;
    }
    //pred_p->left = pred->right;
    if (pred_p->right == pred)
       pred_p->right = pred->left;
    else
       pred_p->left = pred->left;
    t->key = pred->key;
    t = pred;
}

when 35
When 18
When num 7 and I checked the all examples, 18, 35, 7

#5. My Learning Points

I was curious why the `free` part was commented out. By running the program, I realized that the nodes were not dynamically allocated but declared as static/global variables, and the exit code showed garbage values, indicating that the program did not terminate properly.

At first, I only thought about finding the successor and predecessor from the child nodes, but while working on this assignment, I realized that it is also possible to find them by moving up to the parent nodes.

Next time, I would like to practice this on Baekjoon using Java, which is the language I normally use, to get more hands-on experience.

Appendix

'컴퓨터공학과 > Data structures' 카테고리의 다른 글

Assignment06 Technical Report  (0) 2025.11.10
[자료구조] Priority, Heap  (0) 2025.11.05
Assignment04_Technical report  (0) 2025.10.10
[자료구조] List  (0) 2025.10.08
Assignment03 Technical Report  (0) 2025.10.02

티스토리툴바