UNIT: TREES

1. Binary Trees

 Definition of Binary Tree

 Basic Terminology (root, parent, child, leaf, level, height, etc.)
 Operations on Binary Trees

2. Binary Tree Representation

 Node Representation (Linked Representation)

 Implicit Array Representation of Binary Trees

3. Binary Tree Traversals

 Tree Traversal Concepts

 Types of Traversals:
o Preorder Traversal
o Inorder Traversal
o Postorder Traversal

4. Threaded Binary Trees

 Concept of Threaded Binary Trees

 Traversal of Threaded Binary Trees

5. Applications of Trees

 Practical Applications of Binary Trees

6. Binary Search Trees (BST)

 Definition of Binary Search Tree

 Insertion of a Node in a BST
 Deletion of a Node from a BST
 Efficiency of Binary Search Tree Operations
Binary Tree – Definitions and Terminology

1. Definition of a Binary Tree

A binary tree is a finite set of elements (nodes) that is either:

1. Empty, or
2. Consists of:
o A single node called the root
o Two disjoint binary trees called the left subtree and right subtree

👉 Each subtree itself is a binary tree.

👉 Either subtree may be empty.

🔹 Important Point
Each element of a binary tree is called a node.

Example
A
/ \
B C
/ \ \
D E F

 Root = A
 Left subtree of A = Tree rooted at B
 Right subtree of A = Tree rooted at C

2. Root, Subtrees, and Nodes

 Root: The topmost node of the tree
 Left Subtree: Binary tree connected to the left of root
 Right Subtree: Binary tree connected to the right of root
 Node: Each element in the tree

🔹 Empty subtree is represented by the absence of a branch.

3. Parent–Child Relationship
 If A is the root and B is the root of its left or right subtree:
o A is the father (parent) of B
o B is the son (child) of A

Types of children:

 Left son
 Right son

Example
A
/ \
B C

 A is father of B and C
 B is left son of A
 C is right son of A

4. Leaf Node
A leaf is a node that has no sons (no children).

🔹 Leaf nodes have both left and right subtrees empty.

Example
A
/ \
B C
/
D

 Leaf nodes = B and D

5. Ancestor and Descendant

 Node n1 is an ancestor of node n2 if:
o n1 is the father of n2, OR
 on1 is the father of some ancestor of n2
 Node n2 is a descendant of node n1.

Example
A
/ \
B C
/
D

 A is ancestor of D
 D is descendant of A
 B is neither ancestor nor descendant of C

6. Left Descendant and Right Descendant

 Left Descendant:
o A node is a left descendant if it is:
 The left son of a node, OR
 A descendant of the left son
 Right Descendant:
o A node is a right descendant if it is:
 The right son of a node, OR
 A descendant of the right son

7. Sibling (Brother) Nodes

Two nodes are called brothers (siblings) if:

 They have the same father

 One is the left son and the other is the right son

Example
A
/ \
B C

 B and C are brothers

8. Direction in Binary Trees
In computer science:

 Root is at the top

 Leaves are at the bottom
 Moving from root to leaves → Descending
 Moving from leaves to root → Climbing

9. Strictly Binary Tree

A binary tree is called strictly binary if:

✔ Every non-leaf node has exactly two children

Example (Strictly Binary)

A
/ \
B C
/ \ / \
D E F G

Not Strictly Binary

A
/ \
B C
/
D

(C has only one child)

🔹 Property
A strictly binary tree with n leaves always has:

2n−1 nodes2n - 1 \text{ nodes}2n−1 nodes

10. Level of a Node

 Root is at level 0
 Level of any other node = level of its father + 1

Example
A (0)
/ \
 B (1) C (1)
\
D (2)

11. Depth of a Binary Tree

 Depth = maximum level of any leaf
 Equal to the longest path from root to a leaf

Example

If deepest leaf is at level 3 →

✔ Depth = 3

12. Complete Binary Tree

A complete binary tree of depth d is a strictly binary tree where:

✔ All leaves are at the same level d

Properties

 Number of nodes at level l ≤ 2l2^l2l

 Total nodes:

2(d+1)−12^{(d+1)} - 12(d+1)−1

Example (Depth = 3)
Total nodes = 2⁴ − 1 = 15
 Operations on Binary Trees
Operations on a binary tree are basic functions that allow us to access, navigate, and
construct a binary tree.

Let p be a pointer to a node nd in a binary tree.

1. Access Operation
--- info(p)

🔹 Definition
Returns the data (information) stored in the node pointed to by p.

🔹 Purpose
Used to read the value of a node.

🔹 Example

If p points to node containing 10

info(p) → 10

2. Navigation Operations
These operations return pointers to related nodes in the tree.

--- left(p)

🔹 Returns a pointer to the left child of node p

🔹 Returns NULL if no left child exists

--- right(p)

🔹 Returns a pointer to the right child of node p

🔹 Returns NULL if no right child exists

--- father(p)
🔹 Returns a pointer to the parent (father) of node p
🔹 Returns NULL if p is the root node

--- brother(p)

🔹 Returns a pointer to the sibling (brother) of node p

🔹 Returns NULL if:

 p is the root, or
 p has no sibling

Example Tree
A
/ \
B C
Operation Result
left(A) B
right(A) C
father(B) A
brother(B) C
father(A) NULL

3. Logical (Boolean) Operations

These functions return true or false.

isleft(p)

🔹 Returns true if node p is the left child of its parent

🔹 Returns false otherwise

isright(p)

🔹 Returns true if node p is the right child of its parent

🔹 Returns false otherwise

Example
 A
/ \
B C
Function Result
isleft(B) true
isright(B) false
isright(C) true
isleft(A) false

4. Implementing Logical Operations

These operations can be implemented using left(), right(), and father().

Implementation of isleft(p)
q = father(p);
if (q == NULL)
return false; // p is root
if (left(q) == p)
return true;
return false;

5. Tree Construction Operations

These operations help in creating and building a binary tree.

1. maketree(x)

🔹 Creates a new binary tree with one node only

🔹 The node contains value x
🔹 Returns a pointer to the newly created root

🔹 Example

p = maketree(10);

Tree created:

10

setleft(p, x)
🔹 Creates a left child for node p
🔹 Node p must NOT already have a left child

Steps:

1. Create a new node

2. Store x in it
3. Link it as left child of p

setright(p, x)

🔹 Creates a right child for node p

🔹 Node p must NOT already have a right child

🔹 Same logic as setleft, but for right side

Example Construction
p = maketree(1);
setleft(p, 2);
setright(p, 3);

Resulting Tree:

1
/ \
2 3

Binary Tree Representations

Binary tree representation refers to how a binary tree is stored in memory so that its nodes
and relationships (parent–child) can be accessed efficiently.

There are two major ways to represent a binary tree:

1. Linked (Node) Representation

2. Implicit (Sequential / Array) Representation

1. Linked (Node) Representation of Binary Trees

In this method, each node explicitly stores pointers to its related nodes.

Basic Idea

 Each node is stored separately

 Nodes are connected using pointers
 Similar to linked lists, but with two child pointers

1.1 Structure of a Node

Each node contains:

 info → data stored in the node

 left → pointer to left child
 right → pointer to right child
 father → pointer to parent

A) Linked Array Representation

Node Declaration (Array Based)
#define NUMNODES 500

struct nodetype {
int info;
int left;
int right;
int father;
};

struct nodetype node[NUMNODES];

Here:
  Nodes are stored in an array
 Pointers are indices of the array
 -1 or 0 is used to represent NULL

Implementing Basic Operations

Operation Implementatio
n
info(p) node[p].info
left(p) node[p].left
right(p) node[p].right
father(p) node[p].father

Identifying Root and Children

 Root node → father = -1

 External pointer usually points to the root

B) Dynamic Node Representation

Node Declaration (Pointer Based)
struct nodetype {
int info;
struct nodetype *left;
struct nodetype *right;
struct nodetype *father;
};

typedef struct nodetype *NODEPTR;

Characteristics

 Nodes created using malloc

 No fixed size
 No available list required
 More flexible

Implementing Operations
 Operation Implementatio
n
info(p) p->info
left(p) p->left
ight(p) p->right
father(p) p->father

2. Implicit (Sequential / Array) Representation

This method stores a binary tree in an array without pointers.

Key Requirement

 Tree must be almost complete

2.1 Indexing Rules

In C (0-based indexing):

Node Index Formula

Root 0
Left child of p 2p + 1
Right child of 2p + 2
p
Parent of p (p − 1) / 2

Example
A
/ \
B C
/ \
D E
Nod Index
e
A 0
B 1
C 2
D 3
E 4
3. Internal and External Nodes
 Internal nodes → non-leaf nodes
 External nodes → leaf nodes

Optimization

 Leaves may store only info

 Internal nodes store left and right
 Saves memory (leaves are usually many)
 Binary Tree Traversal
1. Introduction
Binary tree traversal is the process of visiting every node of a binary tree exactly once in
a systematic order.

Traversal is required for:

 Printing nodes
 Searching data
 Evaluating expressions
 Copying or deleting trees

2. Types of Binary Tree Traversals

There are three basic traversal methods:

1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal

These traversals are defined recursively based on:

 Root
 Left subtree
 Right subtree

4. Preorder Traversal
Definition

In Preorder Traversal, nodes are visited in the order:

Root → Left Subtree → Right Subtree

Algorithm

1. Visit the root node

2. Traverse left subtree
3. Traverse right subtree
Recursive C Program
void pretrav(NODEPTR tree)
{
if (tree != NULL) {
printf("%d\n", tree->info); /* visit root */
pretrav(tree->left); /* traverse left subtree */
pretrav(tree->right); /* traverse right subtree */
}
}

Example
A
/ \
B C
/ \
D E

Preorder Output:
ABDEC

Applications

✔ Copying trees
✔ Prefix expression evaluation

5. Inorder Traversal
Definition

In Inorder Traversal, nodes are visited in the order:

Left Subtree → Root → Right Subtree

Algorithm

1. Traverse left subtree

2. Visit root node
3. Traverse right subtree
Recursive C Program
void intrav(NODEPTR tree)
{
if (tree != NULL) {
intrav(tree->left); /* traverse left subtree */
printf("%d\n", tree->info); /* visit root */
intrav(tree->right); /* traverse right subtree */
}
}

Example
A
/ \
B C
/ \
D E

Inorder Output:
DBEAC

Applications

✔ Produces sorted order in Binary Search Tree

✔ Expression tree evaluation (infix)

6. Postorder Traversal
Definition

In Postorder Traversal, nodes are visited in the order:

Left Subtree → Right Subtree → Root

Algorithm

1. Traverse left subtree

2. Traverse right subtree
3. Visit root node

Recursive C Program
void posttrav(NODEPTR tree)
{
if (tree != NULL) {
posttrav(tree->left); /* traverse left subtree */
posttrav(tree->right); /* traverse right subtree */
printf("%d\n", tree->info); /* visit root */
}
}

Example
A
/ \
B C
/ \
D E

Postorder Output:
DEBCA

Applications

✔ Deleting trees
✔ Postfix expression evaluation
Applications of Trees (Detailed Notes)

1. Hierarchical Data Representation

Explanation

Trees naturally represent hierarchical relationships, where:

 One node acts as a parent

 Other nodes act as children

Each element (node) can have multiple sub-elements.

Example

 Organization Structure

CEO
├── Manager 1
│ ├── Employee A
│ └── Employee B
└── Manager 2
└── Employee C

Why Trees?

✔ Clear parent–child relationship

✔ Easy traversal from top to bottom

2. File System in Operating Systems

Explanation

Computer file systems use tree structures to organize:

 Directories (folders)
 Subdirectories
 Files

Example
C:
├── Program Files
├── Users
│ └── Student
 │ ├── Documents
│ └── Downloads
└── Windows

Advantages

✔ Fast file searching

✔ Efficient storage management
✔ Easy insertion and deletion

3. Expression Trees (Arithmetic Expressions)

Explanation

Expression trees are used to represent:

 Arithmetic expressions
 Mathematical formulas

Rules

 Operators → internal nodes

 Operands → leaf nodes

Example

Expression: (A + B) * C

*
/ \
+ C
/ \
A B

Applications

✔ Compiler design
✔ Expression evaluation
✔ Infix → Prefix/Postfix conversion

4. Searching and Sorting (Binary Search Trees)

Explanation

Trees like Binary Search Trees (BST) store data such that:
  Left subtree → smaller values
 Right subtree → larger values

Example

Insert: 50, 30, 70, 20, 40

50
/ \
30 70
/ \
20 40

Benefits

✔ Faster search than arrays

✔ Average time: O(log n)

5. Database Indexing
Explanation

Databases use B-Trees and B+ Trees for indexing large data.

Why Trees in Databases?

 Data is stored on disk

 Trees reduce disk access time

Applications

✔ DBMS indexing
✔ File systems
✔ Large data storage

6. Decision Making (Decision Trees)

Explanation

Decision trees help in making choices based on conditions.

Example
Is age > 18?
/ \
Yes No
| |
Can vote Cannot vote

Uses

✔ Machine learning
✔ Artificial intelligence
✔ Expert systems

7. Artificial Intelligence and Game Trees

Explanation

Game trees represent:

 Possible moves in a game

 Outcomes of each move

Examples

 Chess
 Tic-Tac-Toe
 Minimax algorithm

Advantages

✔ Predict future moves

✔ Choose best strategy

8. Compiler Design
Explanation

Compilers use trees to:

 Check syntax
 Analyze grammar
 Generate code

Types
  Parse Tree
 Syntax Tree
 Abstract Syntax Tree (AST)

Benefit

✔ Accurate syntax checking

✔ Efficient code generation

9. Network Routing
Explanation

Trees are used in networks for:

 Spanning trees
 Routing paths

Example

 Minimum Spanning Tree (MST)

 Network broadcast trees

Advantages

✔ Avoid loops
✔ Efficient communication

10. XML / HTML Parsing

Explanation

Web documents are structured as trees.

Example
<html>
<body>
<h1>Title</h1>
<p>Paragraph</p>
</body>
</html>

Tree Representation
  Tags → nodes
 Nested tags → child nodes

Applications

✔ Web browsers
✔ DOM manipulation
✔ XML parsers

11. Memory Management

Explanation

Trees help in:

 Garbage collection
 Memory allocation

Use

✔ Track memory blocks

✔ Free unused memory

12. Computer Graphics

Explanation

Trees are used to represent:

 Scene graphs
 Object hierarchies

Applications

✔ Animation
✔ Game development
Threaded Binary Tree (Simple Detailed
Notes)

1. Why Threaded Binary Tree is Needed

First understand a problem in normal binary trees.

In a normal binary tree, each node has:

 Left pointer
 Right pointer

Sometimes these pointers are NULL.

Example:

A
/ \
B C
/
D

Node D has:

left = NULL
right = NULL

💡 These NULL pointers are wasted memory.

Threaded Binary Tree uses these NULL pointers to store useful links.

2. What is a Threaded Binary Tree?

A Threaded Binary Tree is a binary tree where:

👉 Some NULL pointers are replaced with special pointers called threads.

These threads point to:

 Inorder successor
 Inorder predecessor

Which helps us traverse the tree without using stack or recursion.

3. What is Inorder Traversal?
First understand Inorder Traversal.

Rule:

Left → Root → Right

Example Tree

A
/ \
B C
/ \
D E

Inorder traversal:

D → B → E → A → C

Each node has a next node in inorder sequence.

Example:

D's successor = B
B's successor = E
E's successor = A

Threaded trees store these successor links.

4. Right Threaded Binary Tree

This is the most common type.

Rule

If a node does not have a right child, then:

right pointer → inorder successor

Example

Normal tree:

A
/ \
B C
/
 D

Inorder:

D → B → A → C

Threaded tree links:

[Link] → B
[Link] → A

Diagram idea:

A
/ \
B C
/
D
\
B (thread)

5. How to Identify Threads

Because the right pointer may be

 real child
 thread

So we use a flag.

rthread

If

rthread = TRUE

then

right pointer = thread

If

rthread = FALSE

then

right pointer = real child

6. Node Structure
Simple C structure:

struct nodetype {
int info;
struct nodetype *left;
struct nodetype *right;
int rthread;
};

Meaning

Variable Meaning
info data
left left child
right right child OR thread
rthread tells if right is thread

8. Advantages of Threaded Binary Tree

1️⃣ No recursion required

Traversal becomes simple.

2️⃣ No stack required

Memory saving.

3️⃣ Faster traversal

Because successor is directly available.

4️⃣ Better use of NULL pointers

Unused pointers are converted to useful links.

9. Creating Threaded Tree

(1) maketree(x)
Creates a node.

NODEPTR maketree(int x)
{
NODEPTR p = getnode();
p->info = x;
p->left = NULL;
p->right = NULL;
p->rthread = TRUE;
return p;
}

Meaning

 create node
 no children
 right pointer treated as thread

(2) setleft(p, x)

Insert node on left side.

void setleft(NODEPTR p, int x)

{
NODEPTR q = getnode();
q->info = x;
q->left = NULL;
q->right = p;
q->rthread = TRUE;
p->left = q;
}

Here

[Link] = p

because

p is inorder successor

(3) setright(p, x)

Insert node on right side.

void setright(NODEPTR p, int x)

{
NODEPTR q = getnode();
q->info = x;
q->left = NULL;
q->right = p->right;
q->rthread = TRUE;
 p->right = q;
p->rthread = FALSE;
}

Meaning

 replace thread
 create real right child

10. Array Representation of Threaded Tree

Instead of pointers we use array indexes.

Example node array:

node[1]
node[2]
node[3]

If:

node[p].right = -4

Meaning:

4 = inorder successor

Negative sign indicates thread.

If:

node[p].right = 5

then

5 is real right child

11. Types of Threaded Binary Trees

1️⃣ Right Threaded Tree

NULL right pointer → inorder successor
Most commonly used.

2️⃣ Left Threaded Tree

NULL left pointer → inorder predecessor

Less useful.

3️⃣ Fully Threaded Tree

Both pointers may be threads.

left → predecessor
right → successor

12. Pre-Threaded Binary Tree

Threads store preorder successor.

Traversal order:

Root → Left → Right

This allows preorder traversal without stack.

13. Traversal Using Father Pointer

Another technique.

Each node stores:

pointer to parent

Example:

struct node {
int info;
struct node *left;
struct node *right;
struct node *father;
};
Traversal can go:

child → parent

without stack.

Tree Searching in Binary Search Trees

(BST)
1. Definition of Binary Search Tree
A Binary Search Tree (BST) is a special type of binary tree used for efficient searching and
storing of data.

In a BST, each node contains:

 a key value
 pointers to left and right subtrees

BST Property

For every node with key k:

 All keys in the left subtree are less than k

 All keys in the right subtree are greater than or equal to k

This property ensures that data in the tree is organized in sorted order.

Example
50
/ \
30 70
/ \ / \
20 40 60 80

Here:

 Left of 50 → 30, 20, 40 (smaller values)

 Right of 50 → 70, 60, 80 (larger values)

Example:

20 30 40 50 60 70 80

2. Insertion in a Binary Search Tree

Definition

Insertion in a Binary Search Tree is the process of adding a new node into the tree while
maintaining the BST property.

Steps for Insertion

1. Start from the root node.

2. Compare the new key with the current node.
3. If the key is smaller, move to the left child.
4. If the key is greater, move to the right child.
5. Repeat the process until a NULL position is found.
6. Insert the new node at that position.

Example

Insert the keys:

50, 30, 70, 20, 40

Step 1: Insert 50

50

Step 2: Insert 30

50
/
30

Step 3: Insert 70

50
/ \
30 70

Step 4: Insert 20

50
/ \
30 70
/
20

Step 5: Insert 40

50
/ \
30 70
/ \
20 40
The tree still satisfies the BST property.

3. Deletion in a Binary Search Tree

Definition

Deletion in a Binary Search Tree is the process of removing a node while maintaining the
BST property.

Three cases must be considered during deletion.

Case 1: Node has No Children (Leaf Node)

If the node to be deleted has no children, it can be removed directly.

Example:

Before deletion

50
/ \
30 70
/ \
20 40

Delete 20

After deletion

50
/ \
30 70
\
40

Case 2: Node has One Child

If the node has only one child, the child replaces the deleted node.

Example:

Delete 30

Before
 50
/ \
30 70
\
40

After

50
/ \
40 70

The child 40 moves up to take the place of 30.

Case 3: Node has Two Children

If the node has two children, replace it with its inorder successor.

Inorder Successor

The inorder successor is the smallest node in the right subtree.

Example:

Delete 50

Before

50
\ /
30 70
/ \ / \
20 40 60 80

The inorder successor of 50 is 60.

Replace 50 with 60.

After deletion

60
/ \
30 70
/ \ \
20 40 80
4. Efficiency of Binary Search Tree
Operations
The efficiency of operations such as searching, insertion, and deletion in a Binary Search
Tree depends on the structure of the tree.

Best Case (Balanced Tree)

If the tree is balanced, the height of the tree is approximately log n.

Example

50
\/
30 70
/ \ / \
20 40 60 80

Searching requires fewer comparisons.

Time Complexity

O(log n)

Worst Case (Unbalanced Tree)

If the tree becomes skewed, it behaves like a linked list.

Example

10
\
20
\
30
\
40

Searching requires checking every node.

Time Complexity

O(n)
Average Case
When elements are inserted in random order, the tree is usually partially balanced.

Average time complexity

O(log n)

Advantages of Binary Search Trees

 Efficient searching, insertion, and deletion
 Data remains sorted automatically
 Dynamic structure (can grow or shrink easily)
 Better than arrays for frequent insertions and deletions

Conclusion
A Binary Search Tree is an efficient data structure used for searching and storing data in
sorted order. Operations such as insertion, deletion, and searching are performed based on
comparisons with node keys. The efficiency of these operations depends on the shape of the
tree, ranging from O(log n) in balanced trees to O(n) in skewed trees.