Unit 4: Trees

TREES

A tree is a non-linear, hierarchical data structure used to represent data in a parent–child relationship.

A tree is a collection of nodes connected by edges, with:

One node called root
Zero or more subtrees
No cycles

Basic Terminology Used with Tree

Term	Description
Node	Basic element of a tree
Root	Topmost node
Parent	Immediate predecessor
Child	Immediate successor
Sibling	Nodes with same parent
Leaf Node	Node with no children
Internal Node	Node with at least one child
Edge	Link between nodes
Level	Distance from root
Height	Maximum level of tree
Depth	Distance from root to node
Degree	Number of children
Subtree	Tree within a tree
Forest	Collection of disjoint trees

Binary Tree

A Binary Tree is a tree in which each node has at most two children, called:

Left child
Right child

Types of Binary Trees

Full Binary Tree
Complete Binary Tree
Perfect Binary Tree
Skewed Binary Tree

Binary Tree Representation

Array Representation

Concept

Used mainly for complete binary trees
Root stored at index 1

Index Formula

Left child = 2i
Right child = 2i + 1
Parent = i / 2

Example

For tree:


      A
     / \
    B   C
   / \
  D   E

Array Representation:


Index: 1  2  3  4  5
Data : A  B  C  D  E

Advantages

Simple implementation
No pointer overhead

Disadvantages

Memory wastage for sparse trees
Fixed size

Pointer (Linked List) Representation

Structure of Node

Each node contains:

Data
Pointer to left child
Pointer to right child

Node Structure (C-style)


struct node {
   int data;
   struct node *left;
   struct node *right;
};

Advantages

Dynamic size
Efficient memory usage

Disadvantages

Extra memory for pointers
Slightly complex

Binary Search Tree (BST)

A Binary Search Tree is a binary tree in which:

Left subtree values < Root
Right subtree values > Root

Example


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

Operations

Insertion
Deletion
Searching

Time Complexity

Operation	Average	Worst
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Advantages

Fast searching
Sorted data retrieval

Disadvantages

Performance degrades if unbalanced

Applications

Database indexing
Symbol tables

Complete Binary Tree

A Complete Binary Tree is a binary tree where:

All levels are completely filled
Except possibly the last level
Nodes are filled from left to right

Properties

Efficient array representation
Height = ⌊log₂ n⌋

Applications

Heap
Priority queue

Extended Binary Tree

An Extended Binary Tree (also called Full Binary Tree with external nodes) is formed by:

Replacing each NULL child with a special external node

Characteristics

Every internal node has exactly two children
External nodes represent NULL links

Properties

If:

Internal nodes = n
External nodes = n + 1

Importance

Helps in tree analysis
Used in expression trees

Comparison of Binary Trees

Feature	Binary Tree	BST	Complete Binary Tree
Order Property	No	Yes	No
Shape	Any	Depends	Fixed
Searching	Slow	Fast	Moderate
Applications	General	Searching	Heap

Important Exam Points (MCA)

Tree is non-linear
BST provides ordered structure
Complete Binary Tree suits array representation
Extended Binary Tree has n+1 external nodes
Linked representation is dynamic

Conclusion

Trees are widely used in:

File systems
Databases
Compilers
Artificial Intelligence

Tree Traversal Algorithms

Tree traversal means visiting each node of a tree exactly once in a systematic manner.

Types of Traversal

Inorder Traversal
Preorder Traversal
Postorder Traversal

Inorder Traversal (LNR)

In Inorder traversal, nodes are visited in the order:
Left → Node → Right

Algorithm (Recursive)

Traverse left subtree
Visit root
Traverse right subtree

Pseudocode


Inorder(node):
  if node != NULL:
     Inorder(node.left)
     visit(node)
     Inorder(node.right)

Important Property

In Binary Search Tree, inorder traversal gives sorted order.

Time Complexity

O(n)

Applications

Sorting data using BST
Expression tree evaluation

Preorder Traversal (NLR)

In Preorder traversal, nodes are visited in the order:
Node → Left → Right

Pseudocode


Preorder(node):
  if node != NULL:
     visit(node)
     Preorder(node.left)
     Preorder(node.right)

Applications

Creating copy of tree
Prefix expression generation

Postorder Traversal (LRN)

In Postorder traversal, nodes are visited in the order:
Left → Right → Node

Pseudocode


Postorder(node):
  if node != NULL:
     Postorder(node.left)
     Postorder(node.right)
     visit(node)

Applications

Deleting tree
Postfix expression evaluation

Comparison of Traversals

Traversal	Order	Use
Inorder	LNR	Sorted output (BST)
Preorder	NLR	Tree construction
Postorder	LRN	Tree deletion

Constructing Binary Tree from Traversals

Possible Combinations

Inorder + Preorder
Inorder + Postorder

❌ Preorder + Postorder (not unique)

Construction using Inorder & Preorder

Steps

First element of preorder is root
Find root in inorder
Left part → left subtree
Right part → right subtree
Repeat recursively

Key Exam Point

Inorder traversal is mandatory for unique tree construction.

Binary Search Tree (BST) Operations

Insertion in BST

Rules

If value < root → left subtree
If value > root → right subtree

Time Complexity

Average: O(log n)
Worst: O(n)

Searching in BST

Method

Compare key with root
Traverse left or right accordingly

Complexity

Average: O(log n)
Worst: O(n)

Deletion in BST

Cases

Node with no child (Leaf)
Node with one child
Node with two children

→ Replace with inorder successor/predecessor

Complexity

O(log n) average

Modification in BST

Meaning

Modify data by:

Delete old value
Insert new value

Reason

Direct modification may violate BST property

Threaded Binary Tree

A Threaded Binary Tree uses NULL pointers to store traversal links.

Types

Single Threaded (Left or Right)
Double Threaded

Advantages

No recursion
No stack required
Faster traversal

Applications

Efficient inorder traversal

Huffman Coding using Binary Tree

Huffman Coding is a lossless data compression technique using binary trees.

Algorithm

Create leaf nodes for characters
Assign frequencies
Build tree using minimum frequency nodes
Assign 0 to left, 1 to right

Properties

Prefix code
No ambiguity

Applications

File compression
ZIP, JPEG, MP3

AVL Tree

An AVL Tree is a self-balancing Binary Search Tree.

Balance Factor

B F = H e i g h t (L e f t) - H e i g h t (R i g h t)

Allowed values: –1, 0, +1

Rotations

LL Rotation
RR Rotation
LR Rotation
RL Rotation

Time Complexity

Search, Insert, Delete: O(log n)

Advantages

Guaranteed balanced tree
Faster searching

B-Tree

A B-Tree is a multi-level balanced tree used for disk storage.

Properties

All leaves at same level
Multiple keys per node
Minimum and maximum keys defined by order m

Advantages

Minimizes disk I/O
Efficient for large data

Applications

Database indexing
File systems

AVL Tree vs B-Tree

Feature	AVL Tree	B-Tree
Type	Binary	Multi-way
Balance	Strict	Relaxed
Disk Use	No	Yes
Applications	Memory	Databases

Important MCA Exam Points

Inorder + Preorder → Tree construction
BST inorder traversal → Sorted data
AVL tree maintains balance using rotations
Huffman coding reduces file size
B-Trees used in databases

Conclusion

Tree traversal and advanced trees form the core of data structures.
Mastery of:

Traversals
BST operations
AVL, B-Tree, Huffman coding

is essential for MCA exams and technical interviews.