TREES

 Data Structures Using ‘C’

 

Unit :-5

TREES

Definition: Tree is a hierarchical structure that is used to represent and organize data in the

form of parent child relationship. It consists of nodes (where the data is stored) that are

connected via links.

The following are some real world situations which are naturally a tree.

 Folder structure in an operating system.

 Tag structure in an HTML (root tag the as html tag) or XML document.

Some applications of the trees are:

 XML Parser uses tree algorithms.

 The decision-based algorithm is used in machine learning which works upon the

algorithm of the tree.

 Databases also use tree data structures for indexing.

 Domain Name Server(DNS) also uses tree structures.

 File explorer/my computer of mobile/any computer

 BST used in computer Graphics

 Posting questions on websites like Quora, the comments are a child of questions

Basic Terminologies In Tree:

Node: Elements of a tree is called as Node. From the above example the nodes are

:A,B,C,D,E,F,G

Root Node: The starting node of a tree is called as Root Node.

• Tree will have only one Root Node.

• From the above example the Root node is: A

Edge: The link or connection between two nodes is called as an Edge.

• If there are n nodes the edges are n-1.

• From the above example the edges are: N = 7 nodes, E = 6 edges.

Parent Node: A node with branches from top to bottom is called as Parent node. From the above

example the parent nodes are: A, B, C.

Child Node: A node with edge from bottom to top or the branches of parent node are called as

Child node. From the above example the Child nodes are: B, C, D, E, F, G.

Siblings: The nodes on the same hierarchical level under the same parent node are called as

Siblings. From the above example the Siblings are: B-C: Siblings, D-E: Siblings, F-G: Siblings.

Leaf: A node without child node is called a Leaf. From the above example the Leaf’s are: D, E,

F, G.

Internal Nodes: All nodes other than leaf nodes are called as Internal nodes.

1. Nodes with child node is an internal node.

2. From the above example internal nodes are: A, B, C.

 

Degree of a Node: The number of child nodes represents the degree of a nodes.

Degree of a tree is the highest degree of a node among all the nodes in the tree.

Height: Longest path from leaf node to that node is called as Height. From the above example

the height of (A) is 2.

Depth: Longest path from root node to that node is called as Depth. From the above example the

Depth of (D) is 2, Depth of (g) is 2, Depth of (B) is 1.

Path: Sequence of node from root to leaf is called as Path. From the above example the Path of

(A to D) is: A-B-D, Path of (A to G) is: A-C-G.

Sub-Tree: Node with child node forms a Sub-tree. From the above example the Sub-trees are:

A, B and C, Sub-tree: B, D and E, Sub-tree: C, F and G, Sub-tree: A, B, C, D, E, F, G.

Ancestor Node: A node that is connected to all lower-level nodes is called as Ancestor node.

From the above example the ancestor nodes are: A, B and C.

Terminal Node: A node with degree (0) zero is called as Terminal node. From the above

example the terminal nodes are: D, E, F, G. It is also called as Leaf node.

Non-Terminal Node: A node without degree (0) zero is called as non-Terminal node. From the

above example the non-terminal nodes are: A, B, C.

Level: Every step or hierarchy in a tree is called as Level.

1. Level of a tree starts from 0.

2. Every step of Hierarchy the level will be incremented by 1.

3. Level of tree=2

Binary Tree: A Binary Tree Data Structure is a hierarchical data structure in which each

node has at most two children, referred to as the left child and the right child.

Applications of binary tree:

 Search Algorithms:

Binary trees are fundamental for efficient search algorithms like binary search.

 Sorting Algorithms:

They are used in efficient sorting algorithms like heap sort and tree sort.

 Database Systems:

Binary trees, especially binary search trees, are used for indexing and organizing data in

databases.

 File Systems:

File systems often use tree structures to represent directories and files, with binary trees being

a foundational data structure.

 Compression Algorithms:

Binary trees are used in algorithms like Huffman coding to compress data.

 Decision Trees:

Binary trees are used in machine learning to represent decision-making processes.

 Game AI:

Binary trees can represent possible game moves and are used in game AI algorithms to find

optimal strategies.

Expression Parsing:

Binary trees are used in compilers and interpreters to represent and evaluate mathematical

expressions.

 Routing Tables:

Binary trees can implement routing tables in routers.

 

Types Of Binary Tree :

1. Strictly Binary Tree

2. Full/Complete Binary Tree

 

1. Strictly Binary Tree:

• Strictly binary tree is a binary tree that has non empty left and right sub tree.

• The out degree of every node is either 0 or 2.

• The nodes with 2 children’s are called as internal nodes.

• The nodes with no children’s are called as external nodes.

Full/Complete Binary Tree:

• Full or complete binary tree is a binary tree that contains maximum number of possible nodes

in all levels.

• In a full binary tree, all the leaf’s are at same level.

• In a full binary tree, all internal nodes have equal degree.

• The out degree of every node is 2 except terminal nodes.

Binary Search Tree

Binary Search Tree has at most two children, a left child and a right child, with the left child

containing values less than the parent node and the right child containing values greater than

the parent node. This hierarchical structure allows for efficient searching, insertion,

and deletion operations on the data stored in the tree.

Heap Tree:

A Heap is a complete binary tree data structure that satisfies the heap property: for every node,

the value of its children is greater than or equal to its own value. Heaps are usually used to

implement priority queues, where the smallest (or largest) element is always at the root of the

tree.

Min heap:

Values of parent node is less than or equal to its children

Max heap: values of parent node is greater than or equal to its children

Array representation of a binary tree

In an array representation of a binary tree, nodes are stored in a one-dimensional array, typically

using a level-order traversal, meaning nodes are stored level by level, starting from the root. The

root is placed at index 0, and the left and right children of a node at index i are located at

indices 2i + 1 and 2i + 2, respectively. This method is particularly useful for complete binary

trees where all levels are fully filled except possibly the last level, which is filled from left to

right.

Binary Tree Traversal

• Traversing means visiting each node exactly once in a systematic manner.

• There are three ways of traversing a binary tree they are:

1. PRE ORDER

2. IN ORDER

3. POST ORDER

Rules Of Binary Tree Traversal Are:

1. PRE ORDER: Root-Left Sub tree-Right Sub tree.

2. IN ORDER: Left Sub tree-Root-Right Sub tree.

3. POST ORDER: Left Sub tree-Right Sub tree-Root.

PRE ORDER TRAVERSAL

Root Left Right

 

Pre Order Binary Tree Traversal:

Rules to be followed for the pre-order technique is:

1. Process the root R.

2. Traverse left Subtree of root R in preorder.

3. Traverse the right Subtree of Root R in preorder.

Algorithm Pre -Order (Root):

Step 1: [process the root node]

If root=/NULL, then

Process info[root]

Else

Write “Tree is empty”

Step 2: [Traverse the left Sub tree recursively in preorder]

If left [root =/ NULL]

Call pre-order (left[root])

Step 3: [Traverse the right Sub tree recursively in preorder]

If right[root]=/NULL

Algorithm In-Order (Root):

 

Step 1: [Traverse the left sub tree of the root R in in-order]

If root == NULL, then

Write “Tree is empty”

Step 2: [If left [root=/ NULL]

Call in-order (left[root])

Step 3: [process the root node]

Info[root]

Step 4: [Traverse the (right([root]) Sub tree of the root in in-order]

If right[root]=/NULL

Call In-order (right [root])

Step 5: return

Post Order Binary Tree Traversal:

Left Right Root

Rules to be followed for the post-order technique is:

1. Traverse left Subtree of root R in preorder.

2. Traverse the right Subtree of Root R in preorder.

3. Process the root R.

Algorithm Post-Order (Root):

 

Step 1: [if root=/NULL, then

Write “Tree is empty”

Step 2: [Traverse the left Sub tree recursively in postorder]

if left [root=/ NULL ]

Call post-order (left[root])

Step 3: [Traverse the right Sub tree recursively in postorder]

if right[root]=/NULL

Call post-order (right [root])

Step 4: [process the Root node]

Info[root]

Step 5: return.

Reconstruction of Binary Tree:

In-Order to Pre-Order:

Pre-Order Traversal:- First node is the Root node.

Remaining nodes:- Left sub tree and Right tree.

In-Order Traversal:-Root node is in between nodes of left and right sub tree.

Simple method of constructing a binary tree from Pre-Order to In-Order

traversal is:

 Insert the node from pre order traversal one by one in the tree, starting from the

BEGINNING.

 In in-order traversal, mark the nodes which have been inserted.

 A node is inserted according to the position with respect to marked nodes in In-order

traversal.

Pre-Order: A B D G H C E I F

In-Order: G D H B A I E C F

Constructing a Binary tree from Post-Order and In-Order

Post-Order Traversal:- Last node is the Root node.

Remaining nodes:- Left sub tree and Right tree.

In-Order Traversal:-Root node is in between nodes of left and right sub tree.

Simple method of constructing a binary tree from Post-Order to In-Order

traversal is:

 Insert the node from post order traversal one by one in the tree, starting from the END.

 In in-order traversal, mark the nodes which have been inserted.

 A node is inserted according to the position with respect to marked nodes in In-order

traversal.

 

Post-Order: G H D B I E F C A Start from Last

In-Order: G D H B A I E C F