DSA NOTES
Unit IV
Trees – Terminology, Binary Trees, Binary Search
Trees (BST), Operations, Tree Traversals – Inorder,
Preorder, Postorder (Recursive and Iterative)
Special Thanks :Pratik Lande
Unit 4
Topics
TREES
Introduction to trees: Basic tree concepts
Binary Trees: Concepts & terminologies, Representation of Binary Tree in memory,
Traversing a binary tree
Binary Search Tree: Basic Concepts, BST operations, Concept of Treaded BST
AVL Tree: Basic concepts and rotations of a tree
Why tree?
In singly linked list, traverse is possible only in forward direction node to node
Doubly linked list enhances the traversing by giving facility to traverse in both the
direction: forward and backward.
The circular linked list further provides more flexibility by allowing jumping from last
node to first node.
But in all these data structures, it is not possible to jump from node to any desired node
directly.
To overcome this problem, DS enhances the flexibility of traversing by providing the data
structure called TREE, where one node is connected to several other nodes.
Hence it is possible to access many other nodes from one node.
Introduction to tree data structure
The tree is a nonlinear hierarchical data structure and comprises a
collection of entities known as nodes. It connects each node in the tree data
structure using "edges”, both directed and undirected.
The nodes are present at different levels and are connected by edges.
Between the set of two connected nodes, the one which is at the upper
level is considered a parent, and the lower one is considered a child node.
In Tree in C, a parent node can have many children nodes. The diagram
below shows the structure of the tree in C.
Tree Terminologies
[Link]:
The first node of the binary tree is known as the root node of the binary tree.
There cannot be any tree without a root node, as it is the tree's origin, and the
root node has no parent element.
We cannot have more than one root node in a tree.
2. Edges:
The connecting link between the two nodes is known as the edges of the tree.
It is also referred to as the branch of a tree.
If there are n nodes in a tree, there will be a total of n-1 edges.
3. Ancestors:
An ancestor of a node is any predecessor node on a
path from the root to that node.
The root node doesn’t have any ancestors.
In the tree shown in the next image, nodes 1, 2,
and 5 are the ancestors of node 10.
4. Descendants:
The immediate successor of the given node is
known as a descendant of a node.
In the figure, 10 is the descendant of node 5.
5. Parent Node:
A node that has a connecting link to another node in the level below is known as
a parent node.
In a more formal term, a node that is a predecessor of another node is called a
parent node.
6. Child Node:
Any node connected to a node one level above it is known as the child node.
In formal terms, every node that is a descendant of any node is known as a child
node.
Every node present in the tree can be considered as a child node except the root
node.
7. Siblings:
The children node that shares the same parent node are referred to as siblings.
8. Leaf node:
A node with no child is known as a leaf node.
In trees, leaf nodes are also called external nodes or terminal nodes.
9. Internal Node:
The nodes with at least one child node are known as internal nodes.
Every node (even the root node) is internal except the leaf nodes.
10. External Node:
A node with no child node is considered an external node.
11. Path:
A path between any two nodes of a tree is the sequence of connected nodes along
with the edges between the two nodes.
The path length is the number of nodes present in that path.
In figure below, length of path A-B-E-J is 4.
12. Level of the node:
The level in the tree represents the number of steps from the top/root.
The root node of the tree is said to be at level 0, and as we go downwards the
level increases.
13. Height of a tree:
The height of any node is given by the maximum number of edges from the leaf
node to that particular node.
In the tree, the height of the root node is called "Height of Tree".
14. Depth of a tree:
The depth of any node in the tree is the length of the path from the root node to
that particular node, i.e., The number of nodes between that particular node and
the root node.
15. Subtree:
In the tree in data structures, each child from a node shapes a sub-tree recursively
and every child in the tree will form a sub-tree on its parent node.
Types of Tree in Data Structures
[Link] Tree
[Link] Tree
[Link] Search Tree
[Link] (Adelson Velsky Lindas) Tree
1. General Tree
The general tree is the type of tree where there are no constraints on the hierarchical
structure.
In the general tree, a node can have either 0 or maximum n number of nodes.
There is no restriction imposed on the degree of the node (the number of nodes that a
node can contain).
The topmost node in a general tree is known as a root node.
The children of the parent node are known as subtrees.
There can be n number of subtrees in a general tree.
In the general tree, the subtrees are unordered as the nodes in the subtree cannot be
ordered.
2. Binary Tree
A Binary tree is a non-linear data structure in which a node can have either 0,
1 or maximum 2 nodes.
Each node in a binary tree is represented either as a parent node or a child node.
There can be two children of the parent node, i.e., left child and right child.
In the next figure, it can be observe that each node contains all-most 2 children. If any
node does not contain left or right child then the value of the pointer with respect to that
child would be NULL.
3. Binary Search Tree
A binary search tree is a type of tree that is a more constricted extension of a binary tree
data structure.
The binary search tree has a unique property known as the binary search property.
This states that the value of a left child node of the tree should be less than the parent
node value of the tree. And the value of the right child node should be greater than the
parent node value.
4. AVL Tree
AVL tree is a self-balancing Binary Search Tree (BST) where the difference between
heights of left and right subtrees for any node cannot be more than one.
Here, self-balancing means that balancing the heights of left subtree and right subtree.
This balancing is measured in terms of the balancing factor.
AVL tree satisfies the property of the binary tree as well as of the binary search tree.
The balancing factor can be defined as the difference between the height of the left
subtree and the height of the right subtree.
The balancing factor's value must be either 0, -1, or 1; therefore, each node in the AVL
tree should have the value of the balancing factor either as 0, -1, or 1.
Binary Tree In Details
Types of Binary Tree:
[Link]/Full Binary Tree
[Link] Binary Tree
[Link] Binary Tree
[Link]/Skewed Binary Tree
[Link] Binary Tree
1. Strictly/Full Binary Tree:
The tree can only be considered as the full binary tree if each node must contain
either 0 or 2 children.
The full binary tree can also be defined as the tree in which each node must
contain 2 children except the leaf nodes.
2. Perfect Binary Tree:
A binary tree is said to be ‘perfect’ if all the internal nodes have strictly two
children, and every external or leaf node is at the same level or same depth
within a tree.
3. Complete Binary Tree
A complete binary tree is another specific type of binary tree where all the tree
levels are filled entirely with nodes, except the lowest level of the tree.
Also, in the last or the lowest level of this binary tree, every node should possibly
reside on the left side.
4. Degenerate/Skewed Binary Tree
The degenerate binary tree is a tree in which all the internal nodes have only one
children.
Such trees are similar to a linked list performance-wise.
A skewed binary tree is a pathological/degenerate tree in which the tree is either
dominated by the left nodes or the right nodes.
Thus, there are two types of skewed binary tree: left-skewed binary tree and right-
skewed binary tree.
The tree (a) in next slide is a degenerate binary tree because all the nodes have only one
child. It is also known as a right-skewed tree as all the nodes have a right child only.
The tree (b) is also a degenerate binary tree because all the nodes have only one child. It
is also known as a left-skewed tree as all the nodes have a left child only.
(a) Right Skewed Binary Tree (b) Left Skewed Binary Tree
5. Extended Binary Tree:
The full binary tree is obtained by adding dummy nodes to a binary tree is called
as Extended Binary Tree.
Binary Tree Representations
[Link] representation:
In array representation, binary tree is represented in sequence in memory with
the help of single dimensional array.
For the array representation of binary tree, we will form an array of size 2*L-1
size where L is the number of levels the binary tree.
Now we will move step by step for the array representation of binary tree.
Example 1:
Step 1: First, suppose we have a binary tree with seven nodes
Step 2: Now, for the array representation of binary tree, we have to give numbering
to the corresponding nodes. The standard form of numbering the nodes is to start
from the root node and move from left to right at every level. After numbering the
tree and nodes will look like this:
Step 3: Now as we have numbered from zero you can simply place the
corresponding number in the matching index of an array then the array will look like
this:
That is the array representation of binary tree but this is the easy case as every node
has two child so what about other cases?
Example 2:
Step 1: consider the binary tree given below:
Step 2: While giving a number you are stuck with the cases where you encounter a leaf
node so just make the child node of the leaf nodes as NULL then the tree will look like
this:
Step 3: Now just number the nodes as done above for the array representation of
binary tree after that the tree will look like this:
Step 4: Now we have the number on each node we can easily use the tree for array
representation of binary tree and the array will look like this:
2. Linked list representation:
We use a double linked list to represent a binary tree.
In a double linked list, every node consists of three fields.
First field for storing left child address, second for storing actual data and third
for storing right child address.
In this linked list representation, a node has the following structure:
Binary Tree Structure Linked List Representation of Binary Tree
Traversing binary tree
Refer the experiment on BST
AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and
1.
There are basically four types of rotations which are as follows:
1. L eft rotation
2. Right rotation
3. Left Right rotation
4. Right Left rotation
Where node A is the node whose balance Factor is other than -1, 0, 1.
The first two rotations LR and RR are single rotations and the next two rotations LRR
and RLR are double rotations.
1. Left Rotation:
2. Right Rotation:
3. Left Right Rotation:
Step 1 Step 2 Step 3 Step 4 Step 5
4. Right Left Rotation:
Step 1 Step 2 Step 3 Step 4 Step 5
Create BST using linked list
[Link]
[Link]
binary-search-tree/
[Link]
[Link]
Construct tree from inorder and preorder
[Link]
and-preorder-traversal/
