TREES:

A Tree Abstract Data Type (ADT) is a non-linear data structure that organizes data in a
hierarchical manner.

Tree Terminology:

Terminologies used in Trees

 Root – The top node in a tree.

 Child – A node directly connected to another node when moving away from the Root.

 Parent – Any nodes which has one or more children nodes.

 Siblings – Nodes with the same parent.

 Descendant – Any successor node on the path from root to that node.

 Ancestor – Any predecessor node on the path from root to that node

 Leaf – A node with no children.

 Degree – Number of sub trees of a node.

 Edge – Connection between one node to another.

 Path – A sequence of nodes and edges connecting a node with a descendant.

 Level – The level of a node is defined by 1 + (the number of connections between the node
and the root).
 Height of node – The height of a node is the number of edges on the longest downward
path between that node and a leaf.

 Height of tree – The height of a tree is the height of its root node.

 Depth – The depth of a node is the number of edges from the node to the tree's root node.

BINARY TREE ADT:

A Binary Tree is a type of tree data structure where each node can have a maximum of two
child nodes, a left child node and a right child node.

This restriction, that a node can have a maximum of two child nodes.

Types of Binary Trees

FULL BINARY TREE:

If each node of binary tree has either two children or no child at all.

PERFECT BINARY TREE:

A perfect binary tree in which all leaf nodes are at the same level.
COMPLETE BINARY TREE:

A complete binary tree is a binary tree in which every level except possibly the last node is
completely filled from left to right leaving no gaps.

SKEWED BINARY TREE:

If a tree which is dominated by left child node or right child node is said to be a skewed
binary tree.
Each node of a binary tree has the following 3 parts:

 Data

 Pointer to left child node

 Pointer to right child node

Binary Tree Traversals

Binary tree traversal refers to the process of visiting each node in the tree exactly once in a
systematic way. There are four main types of binary tree traversals: in-order, pre-order, post-
order, and level-order. Each traversal method visits nodes in a different order.

1. In-order Traversal (Left, Root, Right)

In in-order traversal, the nodes are recursively visited in this order: left subtree, root node,
and then the right subtree.

Example:

In-order Traversal: 4, 2, 5, 1, 3

Steps:

 Visit the left subtree: 4

 Visit the root: 2

 Visit the right subtree: 5

 Visit the root: 1

 Visit the right subtree: 3

2. Pre-order Traversal (Root, Left, Right)

In pre-order traversal, the nodes are recursively visited in this order: root node, left subtree,
and then the right subtree
Example:

Pre-order Traversal: 1, 2, 4, 5, 3

Steps:

 Visit the root: 1

 Visit the left subtree: 2

 Visit the left subtree: 4

 Visit the right subtree: 5

 Visit the right subtree: 3

3. Post-order Traversal (Left, Right, Root)

In post-order traversal, the nodes are recursively visited in this order: left subtree, right
subtree, and then the root node.

Example:

Post-order Traversal: 4, 5, 2, 3, 1

Steps:

 Visit the left subtree: 4

 Visit the right subtree: 5

 Visit the root: 2

  Visit the right subtree: 3

 Visit the root: 1

4. Level-order Traversal (Breadth-First)

In level-order traversal, the nodes are visited level by level from left to right. This traversal
uses a queue data structure to keep track of nodes.

Example:

Level-order Traversal: 1, 2, 3, 4, 5

Steps:

 Visit the root: 1

 Visit the nodes at the next level: 2, 3

 Visit the nodes at the next level: 4, 5

Implementation of Binary Tree:

Using Arrays

Construct the root node at index 0

Left child is placed at 2i+1 where i is position of parent.

Right child is placed at 2i+2 where i is position of parent

 A
0

i=0,2i+2=2

i=0,2i+1=1
C
B

i=1,2i+1=3 i=1,2i+2=4

D E

i=3,2i+1=7 i=4,2i+1=9

F
G

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

A B C D E - - F - G

BINARY SEARCH TREE:

A binary search tree (BST) is a type of data structure used in computer science to store and
manage data. In a BST, each node is a part of the tree that holds a value. Each node can have
up to two children nodes. The node at the top is called the root.

The main rule of a BST is that for any node:

 All the values in the left child and its descendants are smaller than the node's value.

 All the values in the right child and its descendants are greater than the node's value.

This structure helps to quickly find, add, or remove values from the tree.
For example, if you want to find a value, you can start at the root and move left or right
depending on whether the value is smaller or larger than the current node, making the
search very efficient.

Example:

Consider the following binary search tree:

 The root node is 10.

 The left child of 10 is 5, and all values in the left subtree (3, 5, 7) are less than 10.

 The right child of 10 is 15, and all values in the right subtree (15, 20) are greater than
10.

1. Insertion
Insertion in binary search tree includes adding a new node in a way that maintains the BST
property: for any node, all values in its left subtree are smaller, and all values in its right
subtree are greater.

Algorithm:

 Start at the root node.

 Compare the value to be inserted with the current node's value.

 If the value is smaller, move to the left child.

 If the value is greater, move to the right child.

 Repeat steps 2-4 until you find an empty spot.

 Insert the new node at the empty spot.

Example:

Insert the value 8 into the following BST:

Step-by-Step Insertion:

 Start at the root (10).

 8 is less than 10, move to the left child (5).

 8 is greater than 5, move to the right child (7).

 8 is greater than 7, move to the right child of 7 (which is empty).

 Insert 8 as the right child of 7.

Result:
3. Searching

Searching in a binary search tree involves finding a node with a given value by leveraging the
BST property to reduce the number of comparisons.

Algorithm:

 Start at the root node.

 Compare the target value with the current node's value.

 If the value is equal, the search is successful.

 If the value is smaller, move to the left child.

 If the value is greater, move to the right child.

 Repeat steps 2-5 until you find the value or reach an empty spot (unsuccessful
search).

Example:Search for the value 8 in the following BST:

Step-by-Step Searching:

 Start at the root (10).

 8 is less than 10, move to the left

child (5).

 8 is greater than 5, move to the

right child (7).

 8 is greater than 7, move to the

right child (8).

 8 is equal to 8, search is
successful.