Module:4 Trees

Dr. Nalliah M

Associate Professor
School of Computer Science and Engineering
Vellore Institute of Technology
Vellore,Tamil Nadu,India.
[Link]@[Link]

September 25, 2025

In linear data structure data is organized in sequential order and in
non-linear data structure data is organized in random order. A tree
is a very popular non-linear data structure used in a wide range of
applications. A tree data structure can be defined as follows...
Tree is a non-linear data structure which organizes data in
hierarchical structure and this is a recursive definition.
A tree data structure can also be defined as follows...
Tree data structure is a collection of data (Node) which is
organized in hierarchical structure recursively.
In tree data structure, every individual element is called as Node.
Node in a tree data structure stores the actual data of that
particular element and link to next element in hierarchical
structure.
In a tree data structure, if we have n number of nodes(vertices)
then we can have a maximum of n − 1 number of links(lines or
edges).
Definition: A tree is finite set of one or more nodes such that
There is a specially designated node called the root.
The remaining nodes are partitioned into n ≥ 0 disjoint sets
T1 , ..., Tn where each of these sets is a tree. T1 , ..., Tn are
called the subtrees of the tree.
Example
Root In a tree data structure, the first node is called as Root
Node. Every tree must have a root node. We can say that the
root node is the origin of the tree data structure. In any tree,
there must be only one root node. We never have multiple
root nodes in a tree.
Edge In a tree data structure, the connecting link between any
two nodes is called as EDGE. In a tree with n number of
nodes there will be a maximum of n − 1 number of edges.
Parent In a tree data structure, the node which is a
predecessor of any node is called as PARENT NODE. In
simple words, the node which has a branch from it to any
other node is called a parent node. Parent node can also be
defined as ”The node which has child / children”.
Example
Child In a tree data structure, the node which is descendant of
any node is called as CHILD Node. In simple words, the node
which has a link from its parent node is called as child node.
In a tree, any parent node can have any number of child
nodes. In a tree, all the nodes except root are child nodes.
Siblings In a tree data structure, nodes which belong to same
Parent are called as SIBLINGS. In simple words, the nodes
with the same parent are called Sibling nodes.

Leaf In a tree data structure, the node which does not have a
child is called as LEAF Node. In simple words, a leaf is a node
with no child.
In a tree data structure, the leaf nodes are also called as External
Nodes. External node is also a node with no child. In a tree, leaf
node is also called as ’Terminal’ node.

Internal Nodes In a tree data structure, the node which has

atleast one child is called as INTERNAL Node. In simple
words, an internal node is a node with atleast one child.
In a tree data structure, nodes other than leaf nodes are called as
Internal Nodes. The root node is also said to be Internal Node if
the tree has more than one node. Internal nodes are also called as
’Non-Terminal’ nodes.

Degree of a vertex in a Tree In a tree data structure, the total

number of children of a node is called as DEGREE of that
Node. In simple words, the Degree of a node is total number
of children it has. The highest degree of a node among all the
nodes in a tree is called as ’Degree of Tree’
Level In a tree data structure, the root node is said to be at
Level 0 and the children of root node are at Level 1 and the
children of the nodes which are at Level 1 will be at Level 2
and so on... In simple words, in a tree each step from top to
bottom is called as a Level and the Level count starts with ’0’
and incremented by one at each level (Step).
Height In a tree data structure, the total number of edges
from leaf node to a particular node in the longest path is
called as HEIGHT of that Node. In a tree, height of the root
node is said to be height of the tree. In a tree, height of all
leaf nodes is ’0’.
Depth In a tree data structure, the total number of egdes
from root node to a particular node is called as DEPTH of
that Node. In a tree, the total number of edges from root
node to a leaf node in the longest path is said to be Depth of
the tree. In simple words, the highest depth of any leaf node
in a tree is said to be depth of that tree. In a tree, depth of
the root node is ’0’.
Path In a tree data structure, the sequence of Nodes and
Edges from one node to another node is called as PATH
between that two Nodes. Length of a Path is total number of
nodes in that path. In below example the path A - B - E - J
has length 4.
Sub Tree In a tree data structure, each child from a node
forms a subtree recursively. Every child node will form a
subtree on its parent node.
Tree Representations

A tree data structure can be represented in two methods. Those

methods are as follows...
List Representation
Left Child - Right Sibling Representation
List Representation

In this representation, we use two types of nodes one for

representing the node with data called ’data node’ and another for
representing only references called ’reference node’. We start with
a ’data node’ from the root node in the tree. Then it is linked to
an internal node through a ’reference node’ which is further linked
to any other node directly. This process repeats for all the nodes in
the tree.
Left Child - Right Sibling Representation

In this representation, we use a list with one type of node which

consists of three fields namely Data field, Left child reference field
and Right sibling reference field. Data field stores the actual value
of a node, left reference field stores the address of the left child
and right reference field stores the address of the right sibling
node. Graphical representation of that node is as follows...

In this representation, every node’s data field stores the actual

value of that node. If that node has left a child, then left reference
field stores the address of that left child node otherwise stores
NULL. If that node has the right sibling, then right reference field
stores the address of right sibling node otherwise stores NULL.
Binary Tree Data structure

In a normal tree, every node can have any number of children. A

binary tree is a special type of tree data structure in which every
node can have a maximum of 2 children. One is known as a left
child and the other is known as right child.
A tree in which every node can have a maximum of two children is
called Binary Tree.
In a binary tree, every node can have either 0 children or 1 child or
2 children but not more than 2 children.
Binary Tree Example (No Arcs)

B C

D E F G
Properties of Binary Tree

A tree on n nodes has exactly n − 1 edges or branches.

In a tree every node except the root has exactly one parent
(and the root node does not have a parent).
There is exactly one path connecting any two nodes in a tree.
The maximum number of nodes in a binary tree of height k is
2k+1 − 1, where k ≥ 0.
Given that we need to store n nodes in a binary tree, the
maximum height is Hmax = n.
The minimum height of a binary tree is determined as follows:
Hmin = ⌊log2 n⌋ + 1.
Types of Binary Trees

There are different types of binary trees and they are...

Strictly Binary Tree In a binary tree, every node can have a
maximum of two children. But in strictly binary tree, every
node should have exactly two children or none. That means
every internal node must have exactly two children. A strictly
Binary Tree can be defined as follows...
A binary tree in which every node has either two or zero
number of children is called Strictly Binary Tree
Strictly binary tree is also called as Full Binary Tree or Proper
Binary Tree or 2-Tree
Strictly Binary Tree Example

B C

D E F G
Strictly binary tree data structure is used to represent
mathematical expressions.
ExpressionTree : (a + b) × (c − d)

+ −

a b c d
Complete Binary Tree

In a binary tree, every node can have a maximum of two children.

But in strictly binary tree, every node should have exactly two
children or none and in complete binary tree all the nodes must
have exactly two children and at every level of complete binary tree
there must be 2level number of nodes. For example at level 2 there
must be 22 = 4 nodes and at level 3 there must be 23 = 8 nodes.
A binary tree in which every internal node has exactly two children
and all leaf nodes are at same level is called Complete Binary Tree.
Complete binary tree is also called as Perfect Binary Tree.
Complete Binary Tree Example

B C

D E F
Complete Binary Tree

B C

D E F G

H I J K L M N O
Extended Binary Tree

A binary tree can be converted into Full Binary tree by adding

dummy nodes to existing nodes wherever required.
The full binary tree obtained by adding dummy nodes to a binary
tree is called as Extended Binary Tree
In below figure, a normal binary tree is converted into full binary
tree by adding dummy nodes (In square node).
From Full Binary Tree to Extended Binary Tree

B C

D E F G

Full Binary Tree

 A

B C

D E F G

Extended Binary Tree

Binary Tree Representations

A binary tree data structure is represented using two methods.

Those methods are as follows...
Array Representation
Linked List Representation
Array Representation

In array representation of a binary tree, we use one-dimensional

array (1-D Array) to represent a binary tree.
The binary tree is complete or almost complete binary tree.
The Root R of the tree is stored in first position of array. If
the parent occupies the position k then the left child occupies
the position 2 ∗ k and right child occupies the position
2 ∗ k + 1 position.
In C, array index start from 0, the address of the left child of
parent at position 2 ∗ k + 1 and the right child of parent at
position 2 ∗ k + 2 respectively.
Array Representation of Binary Tree

In array representation of a binary tree, we use one-dimensional

array (1-D Array) to represent a binary tree.

B C

D E F
Array Representation of Binary Tree

A B C D E F -

0 1 2 3 4 5 6
Example

B C

E
Array Representation of Binary Tree

A B C - E - -

0 1 2 3 4 5 6
Linked List Representation

The binary tree represent using double linked list. If a binary tree is
not complete or almost complete, a better choice to storing it is to
used to linked representation.
 LCA Data RCA

where LCA-Left child address and RCA-Right child address.

Example

B C

D F G H

I J K
Conversion of a General Tree to Binary tree

Any general tree can be represented as a binary tree using the

ALL nodes general tree will be nodes of binary tree.
The root of the binary tree is the root of the general tree.
The left child of a node in the general tree is the left child of
that node in the binary tree.
The right sibling of any node in the general tree is the right
child of that node in the binary tree.
Example
Example
Tree Traversals

Traversal is a process to visit all the nodes of a tree and may print
their values too. Because, all nodes are connected via edges (links)
we always start from the root (head) node. That is, we cannot
randomly access a node in a tree. There are three ways which we
use to traverse a tree.
In-order traversal
Pre-order Traversal
Post-order Traversal
Level-order Traversal
In-order traversal

In this traversal method, the left subtree is visited first, then the
root and later the right sub-tree. We should always remember that
every node may represent a subtree itself. If a binary tree is
traversed in-order, the output will produce sorted key values in an
ascending order.
We start from A, and following in-order traversal, we move to its
left subtree B. B is also traversed in-order. The process goes on
until all the nodes are visited.

The output of inorder traversal of this tree is given as below.

In-order:D → B → E → A → F → C → G .
In-order Pseudocode

In-Order time Complexity: If x is the root of an n-node subtree,

then the call INORDER-TREE-WALK(x) takes Θ(n) time.
Pre-Order Traversal

In this traversal method, the root node is visited first, then the left
subtree and finally the right subtree.

We start from A, and following pre-order traversal, we first visit A

itself and then move to its left subtree B. B is also traversed
pre-order. The process goes on until all the nodes are visited. The
output of pre-order traversal of this tree will be:
A → B → D → E → C → F → G.
Pre-Order Pseudocode
Post-order Traversal

In this traversal method, the root node is visited last, hence the
name. First we traverse the left subtree, then the right subtree and
finally the root node.
We start from A, and following Post-order traversal, we first visit
the left subtree B. B is also traversed post-order. The process goes
on until all the nodes are visited. The output of post-order
traversal of this tree will be: D → E → B → F → G → C → A.
Level-Order Traversal
Level order Traversal is implemented with circular queue. In this
order, we visit the root first, then root’s left child followed by root’s
right child. We continue in this manner, visiting the nodes at each
new level from left most to right most nodes. We begin by adding
root to the queue. The function operates by deleting the node at
the front of the queue, printing out the node’s data field, and
adding the node’s left and right children to the queue. The level
order traversal for below arithmetic expression is + ∗ E ∗ D/CAB.
To construct a unique binary Inorder traversal together
with either Postorder or Preorder must be given.

Let us suppose we have given in-order and pre-order traversal of a

binary tree. We don’t know how original binary tree look alike. So
we’ll try to reconstruct original binary tree from given in-order and
pre-order traversal.
Procedure

Step 1 Use the pre-order sequence to determine the root node

of the tree. The first element would be the root node.
Step 2 Elements on the left side of the root node in the
in-order traversal sequence form the left sub-tree of the root
node. Similarly, elements on the right side of the root node in
the in-order traversal sequence form the right sub-tree of the
root node.
Step 3 Recursively select each element from pre-order
traversal sequence and create its left and right sub-trees from
the in-order traversal sequence. Look at below figure which
constructs the tree from its traversal results.
Example

Give In–order Traversal: D B E A F C G

Pre–order Traversal: A B D E C F G
For example, consider the traversal results given below:
In–order Traversal: D B E A F C G
Pre–order Traversal: A B D E C F G
Problem

Construct a binary tree whose preorder traversal is 5 7 4 8 6 1 9 2

3 and inorder traversal is 4 7 5 6 1 8 2 9 3. The post-order
traversal of the binary tree is ?

This is final binary tree which we have reconstructed from given

inorder and preorder. So post-order traversal is given as: 4 7 1 6 2
3985
Construction of binary tree from given Postorder and inorder
traversal is same as that constructing binary tree from preorder
and inorder, but in case of postorder traversal we scan the given
traversal from right to left and in case of preorder we scan the
given traversal from left to right. So I will not discuss in much
detail. We will solve the right and left subtree in parallel.
Example
Now consider the in-order traversal and post-order traversal
sequences of a given binary tree. Before constructing the binary
tree, remember that in post-order traversal the root node is the
last node. Rest of the steps will be the same as mentioned below
figure:
Example

Given In–order Traversal: D B H E I A F J C G

Post order Traversal: D H I E B J F G C A
You are given two traversal Inorder and Postorder of Binary tree
as: Inorder : 3 2 8 5 7 9 6 4 1 Postorder : 2 3 5 8 6 1 4 9 7 Binary
search tree with its Preorder traversal is ?
Expression Tree

An expression tree is a tree built up from the simple operands as

the leaves of binary tree and operators as the non-leaves of binary
tree. It is a special kind of binary tree in which:-
Each leaf node contains single operand.
Each non-leaf node contains a single binary operator.
The left and right subtrees of an operator node represent
sub-expression that must be evaluated before applying the
operator at the root of the subtree.
The levels in a binary expression tree represent the precedence of
operators. The operators at the lower level must be evaluated first
and then the operators at the next level and so on and at the last
operator at the root node is applied and there by the expression is
evaluated.
 ∗

− +

a b c d

Prefix expression is ∗ − ab + cd similar to preorder traversal

Postfix expression is : ab − cd + ∗ similar to postorder
traversal
Construction of Expression Tree:

From prefix and infix expression

(1). Read the prefix expression, the first element becomes the root.
(2). Now scan the infix expression till you get an element found in
step 1. Place all the elements left of this element to the left of
it and other element to right of it.
(3). Repeat steps 1 and 2 till all the elements from infix expression
gets placed in tree.
(4). stop.
Constructing Expression Tree from Prefix and Infix

Given:
Prefix: * + A B - C D
Infix: A + B * C - D
Procedure:
1 First prefix element * becomes root.
2 In infix, locate *. Left: A + B, Right: C - D
3 Next prefix: +  root of left subtree. In infix left: locate +.
Left: A, Right: B
4 Next prefix: -  root of right subtree. In infix right: locate -.
Left: C, Right: D
Resulting Tree:

+ -

A B C D
From infix and postfix expression.
(1). Read the postfix expression, the last element becomes the root.
(2). Now scan the infix expression till you get an element found in
step1. Place all the elements left of this element to the left of
it and other element to right of it.
(3). Repeat steps 1 and 2 till all the elements from infix expression
get placed in tree.
(4). Stop
Constructing Expression Tree from Infix and Postfix

Given:
Infix: A + B * C - D
Postfix: A B C * + D -
Procedure:
1 Last postfix element - becomes root.
2 In infix, locate -. Left: A + B * C, Right: D
3 Next postfix: +  root of left subtree. In infix left: locate +.
Left: A, Right: B * C
4 Next postfix: *  root of right subtree of +. In infix: locate
*. Left: B, Right: C
Resulting Tree:

+ D

A *

B C
From a given postfix expression..
(1). Read the element from postfix expression from left to right
(2). If it is an operand then push address of this node onto stack
go to step 1.
(3). If the element is an operator then pop twice which gives the
address of the two operands. Create a new node for this
operator and attach the operand to the left and right branch.
Push the address of this node onto stack .
(4). If all the elements from postfix expression are not read then go
to step 1.
(5). Pop the contents of stack which give the root address of
expression tree.
(6). Stop.
Expression Tree Construction from Postfix
Postfix Expression:A B C * + D -
Algorithm:
1 Scan from left to right.

2 If operand: push onto stack.

3 If operator: pop two operands, create node, push result.

4 Repeat until all symbols are processed.

5 Final stack pop gives root of expression tree.

Step-by-Step Construction:
Push: A, B, C
Operator *  pop B, C  create node ‘*‘ with B (left), C
(right)
Push: ‘*‘
Operator +  pop A, ‘*‘  create node ‘+‘ with A (left), ‘*‘
(right)
Push: ‘+‘ and then Push: D
Operator -  pop ‘+‘, D  create node ‘-‘ with ‘+‘ (left), D
Final Expression Tree:

+ D

A *

B C
Example

Construct expression tree from following expressions:-

Postfix expression: 5 3 2 ˆ * 3 7 3 + 10 / + /
Infix expression :- (5*3 ˆ 2)/(3+(7+3)/10)
From postfix we get root i.e. /
/

* +

5 ∧ 3 /

3 2 + 10

7 3
Detail explanation for the above example
Given:
Postfix: 5 3 2 ^ * 3 7 3 + 10 / + /
Infix: (5 * 3 ^ 2) / (3 + (7 + 3) / 10)

Step-by-Step Construction:
1 Push: 5, 3, 2

2 Operator ˆ  pop 3, 2 create node ˆ with 3 (left), 2

(right)
3 Push: ˆ

4 Operator *  pop 5, ˆ create node * with 5 (left), ˆ

(right)
5 Push: *

6 Push: 3, 7, 3

7 Operator +  pop 7, 3 create node + with 7 (left), 3

(right)
1 Push: +
2 Push: 10
3 Operator /  pop +, 10  create node / with + (left), 10
(right)
4 Push: /
5 Operator +  pop 3, /  create node + with 3 (left), /
(right)
6 Push: +
7 Operator /  pop *, +  create node / with * (left), +
(right)
Final Expression Tree:

* +

5 ˆ 3 /

3 2 + 10

7 3
Example
Given an expression, E= ((a + b) – (c * d)) % ((e ∧ f) / (g – h)),
construct the corresponding binary tree.
%

- /

+ * ∧ -

a b c d e f g h
Binary Search Trees

Binary search tree, also known as an ordered binary tree, is a

variant of binary trees in which the nodes are arranged in an order.
In a binary search tree, all the nodes in the left sub-tree have a
value less than that of the root node. Correspondingly, all the
nodes in the right sub-tree have a value either equal to or greater
than the root node. The same rule is applicable to every sub-tree
in the tree.
Binary Search Tree Representation: Binary Search tree exhibits a
special behavior. A node’s left child must have value less than its
parent’s value and node’s right child must have value greater than
it’s parent value.
Definition

A binary search tree (BST) is a binary tree. It may be empty. If it

is not empty,then all nodes follows the below mentioned properties
Every element has a unique key.
The keys in a nonempty left subtree (right subtree) are
smaller (larger) than the key in the root of subtree.
he keys in a nonempty right subtree larger than the key in the
root of subtree.
The left and right subtrees are also binary search trees.
Example
Problem

Create a binary search tree using the

following data elements: 45, 39, 56, 12, 34, 78, 32, 10, 89, 54, 67, 81
BST Basic Operations

The basic operations that can be performed on binary search tree

data structure, are following
Search-search an element in a binary search tree.
Insert- insert an element into a binary search tree / create a
tree..
Delete-Delete an element from a binary search tree.
Height- Height of a binary search tree.
Search an Element

Let an element k is to search in binary search tree. Start search

from root node of the search tree.
If root is NULL, search tree contains no nodes and search
[Link], compare k with the key in the root.
If k equals the root’s key, terminate search, if k is less than
key value, search element k in left subtree otherwise search
element k in right subtree.
The function search recursively searches the subtrees.
If h is the height of the binary search tree, both
algorithms(Recursive and Iterative) perform search in O(h) time.
Insertion
The very first insertion creates the tree. Afterwards, whenever an
element is to be inserted. First locate its proper location. Start
search from root node then if data is less than key value, search
empty location in left sub tree and insert the data.
Otherwise search empty location in right sub tree and insert the data.
Deletion

Delete operation on binary search tree is more complicated, than

insert and search. Basically, in can be divided into two stages:
Search for a node to delete
if the node(delete) is found, run delete algorithm.
Deletion Operation Cases
Deleting a Leaf node (A node with no children)
Deleting a node with one child.
Deleting a node with two children.
Case-1: Deleting a leaf node
We use the following steps to delete a leaf node from BST.
Find the node to be deleted using search operation.
Delete the node using free function (If it is a leaf) and
terminate the function.
Case-2:Deleting a node with one child

To handle this case, the node’s child is set as the child of the
node’s parent. In other words, replace the node with its child.
if the node is the left child of its parent, the node’s child
becomes the left child of the node’s parent.
if the node is the right child of its parent, the node’s child
becomes the right child of the node’s parent.
Case-3: Deleting a node with two children

To handle this case, replace the node’s value with its in-order
predecessor (largest value in the left sub-tree) or in-order successor
(smallest value in the right sub-tree). The in-order predeces-
sor or the successor can then be deleted using any of the above cases.
Deletion Algorithm
In Step 1 of the algorithm, we first check if TREE=NULL, because
if it is true, then the node to be deleted is not present in the tree.
However, if that is not the case, then we check if the value to be
deleted is less than the current node’s data. In case the value is
less, we call the algorithm recursively on the node’s left sub-tree,
otherwise the algorithm is called recursively on the node’s right
sub-tree.
Note that if we have found the node whose value is equal to VAL,
then we check which case of deletion it is. If the node to be
deleted has both left and right children, then we find the in-order
predecessor of the node by calling findLargestNode(TREE -¿
LEFT) and replace the current node’s value with that of its
in-order predecessor. Then, we call Delete(TREE -¿ LEFT, TEMP
-¿ DATA) to delete the initial node of the in-order predecessor.
Thus, we reduce the case 3 of deletion into either case 1 or case 2
of deletion.
If the node to be deleted does not have any child, then we simply
set the node to NULL. Last but not the least, if the node to be
deleted has either a left or a right child but not both, then the
current node is replaced by its child node and the initial child node
is deleted from the tree.
The delete function requires time proportional to the height of the
tree in the worst case. It takes O(logn)
time to execute in the average case and Ω(n) time in the worst case.
Minimum/maximum

To find the minimum element in a tree, we start at the root, and

take its left child. Then we look at the left child of that left child,
etc. We keep going until we reach NIL, and then we return the last
non-NIL node in the sequence. This pseudocode generalizes this
procedure to find the minimum element in a subtree rooted at a
given non-NIL node x.
This pseudocode generalizes this procedure to find the minimum
element in a subtree rooted at a given non-NIL node x.
This is correct because on any iteration of the loop:
If x has no left subtree, then x has the smallest key in the
subtree rooted at x.
If x has a left subtree, then the smallest key in the subtree
rooted at x must be in the left subtree of x, by the binary
search tree property.
The Minimum and Maximum functions also run in O(h) time,
where h is the height of the tree.
Finding the k-th Smallest in BST

Method : Using Inorder Traversal (O(n) me and O(h) auxiliary

space)
The In-order Traversal of a BST traverses the nodes in
increasing order.
So the idea is to traverse the tree in Inorder. While traversing,
keep track of the count of the nodes visited.
If the count becomes k, print the node.
Finding the k-th Smallest in BST:Example

Given the root of a binary search tree and k as input, and k-th
smallest element in BST. For example, in the following BST, if k=
3, then the output should be 10, and if k = 5, then the output
should be 14.

Inorder traversal of BST: 4 8 10 12 14 20 22

Here, the 3-th smallest element is 10.
Thank you