Tree

Tree
• The tree data structure is a kind of hierarchal data arranged in a tree-like
structure.
• It consists of a central node, structural nodes, and sub nodes, which are
connected via edges.
• We can also say that tree data structure has roots, branches, and leaves
connected with one another.  
• A tree is non-linear and a hierarchical data structure consisting of a
collection of nodes such that each node of the tree stores a value, a list
of references to nodes (the “children”).
• Trees can be implemented using array or linked list.
• Recursive Definition: : A tree consists of a root, and zero or more
subtrees T1, T2, … , Tk such that there is an edge from the root of the
tree to the root of each subtree.
• Tree is a non-linear data structure
which organizes data in a
hierarchical structure.
• A Graph is a data structure which
consists of a finite set of vertices(or
nodes) and set of Edges which
connect a pair of nodes.
• A tree is a connected graph without
any circuits.
• If in a graph, there is one and only
one path between every pair of
vertices, then graph is called as a
tree.
Basic Terminology In Tree Data Structure:
• Parent Node: The node which is a predecessor of a node is called the
parent node of that node. {2} is the parent node of {6, 7}.
• Child Node: The node which is the immediate successor of a node is called
the child node of that node. Examples: {6, 7} are the child nodes of {2}.
• Root Node: The topmost node of a tree or the node which does not have
any parent node is called the root node. {1} is the root node of the tree
• Degree of a Node: The total count of subtrees attached to that node is
called the degree of the node. The degree of a leaf node must be 0. The
degree of a tree is the maximum degree of a node among all the nodes in
the tree. The degree of the node {3} is 3.
• Leaf Node or External Node: The nodes which do not have any child
nodes are called leaf nodes. {6, 14, 8, 9, 15, 16, 4, 11, 12, 17, 18,
19} are the leaf nodes of the tree.
• Ancestor of a Node: Any predecessor nodes on the path of the root
to that node are called Ancestors of that node. {1, 2} are the parent
nodes of the node {7}
• Descendant: Any successor node on the path from the leaf node to
that node. {7, 14} are the descendants of the node. {2}.
• Sibling: Children of the same parent node are called siblings. {8, 9,
10} are called siblings.
• Depth of a node: The count of edges from the root to the node. Depth
of node {14} is 3.
• Height of a node: The number of edges on the longest path from that
node to a leaf. Height of node {3} is 2.
• Height of a tree: The height of a tree is the height of the root node i.e
the count of edges from the root to the deepest node. The height of
the above tree is 3.
• Level of a node: The count of edges on the path from the root node to
that node. The root node has level 0.
• Internal node: A node with at least one child is called Internal Node.
 Properties-
• The important properties of tree data structure are-
• There is one and only one path between every pair of vertices in a
tree.
• A tree with n vertices has exactly (n-1) edges.
• A graph is a tree if and only if it is minimally connected.
• Any connected graph with n vertices and (n-1) edges is a tree.
Internal Node-
 
•The node which has at least one child is called as an internal node.
•Internal nodes are also called as non-terminal nodes.
•Every non-leaf node is an internal node.
Leaf nodes
Level-
• In a tree, each step from top to bottom is called as level of a tree.
• The level count starts with 0 and increments by 1 at each level or step.
Height-
 • Total number of edges that lies on the longest path from any leaf
node to a particular node is called as height of that node.
• Height of a tree is the height of root node.
• Height of all leaf nodes = 0
Forest- 
• A forest is a set of disjoint trees.
 Types of Tree data structures
• The different types of tree data structures are as follows:
1. General tree
• A general tree data structure has no restriction on the number of nodes. It means that a parent
node can have any number of child nodes.  
2. Binary tree  
• A node of a binary tree can have maximum number of two child nodes. In the given tree diagram,
node B, D, and F are left children, while E, C, and G are the right children.  
3. Balanced tree
• If the height of the left sub-tree and the right sub-tree are equal or differs at most by 1, the tree
is known as balanced tree data structure.  
4. Binary search tree
• As the name implies, binary search trees are used for various searching and sorting algorithms. 
Binary Tree-
• Binary tree is a special tree data structure in which each node can have at most 2
children.
• In a binary tree, each node has either 0 child or 1 child or 2 children.
Full / Strictly Binary Tree-
A binary tree in which every node has either 0 or 2 children is called as a Full binary tree.
Complete / Perfect Binary Tree-
• A complete binary tree is a binary tree that satisfies the following 2
properties-
• Every internal node has exactly 2 children.
• All the leaf nodes are at the same level
 Binary Tree Properties-
1. Maximum number of nodes in a binary tree of height H= 2H+1 – 1
• Example:
Maximum number of nodes in a binary tree of height 3
= 23+1 – 1
= 16 – 1
= 15 nodes
Derivation
20 Total number of nodes:
20 + 21 + 22……………..2h
=1(2H+1 -1)/2-1 //using GP series
formula
=2H+1 -1
21
A(rn -1)/r-1

22
.

2H
2) Total Number of leaf nodes in a Binary Tree= Total Number of
nodes with 2 children + 1.

• Number of leaf nodes = 3

• Number of nodes with 2 children = 2
• Number of leaf nodes is one greater than number of nodes with 2
children.
3) If a complete binary tree have n nodes then height of
the tree log(n)
• 2h+1 -1=n
• 2h+1 =n+1
• Take log both sides on base 2
• log2 2h+1 =log2(n+1)
• H+1=log(n+1)
• H=log(n+1)-1
• ͌log(n)
Tree traversal techniques: 
• Unlike linear data structures (Array, Linked List, Queues, Stacks, etc)
which have only one logical way to traverse them, trees can be
traversed in different ways.
• Following are the generally used ways for traversing trees.
• Preorder Traversal
• Inorder Traversal
• Postorder Traversal
1. Preorder Traversal-

Algorithm-
• Visit the root
• Traverse the left sub tree i.e. call Preorder (left sub tree)
• Traverse the right sub tree i.e. call Preorder (right sub tree)
 
Root → Left → Right
Example-
shortcut
2. Inorder Traversal-

Algorithm-
•  Traverse the left sub tree i.e. call Inorder (left sub tree)
• Visit the root
• Traverse the right sub tree i.e. call Inorder (right sub tree)
 
Left → Root → Right
Inorder Traversal Shortcut
3. Postorder Traversal-
Algorithm-
•  Traverse the left sub tree i.e. call Postorder (left sub tree)
• Traverse the right sub tree i.e. call Postorder (right sub tree)
• Visit the root

Left → Right → Root
• preorder:: ABDIJFCGKH
• INORDER::IDJBFAGKCH
• POSTORDER::IJDFBKGHCA
PRE:3102654 10 987
IN:012345678910
POST: 021457891063
PRE: ABDEHICFGJ
IN: DBHEIAFCJG
POST:DHIEBFJGCA
 Binary Tree Representations
• A binary tree data structure is represented using two methods. Those
methods are as follows...
• Array Representation
• Linked List Representation
• Consider the following binary tree...
A

C
B

D
F G H

I J K
1. 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.
Consider the above example of a binary tree and it is represented as follows...
1 2 3 4 5 6 7 8 9 10 11 12 13

• To represent a binary tree of depth 'n' using array representation, we need one

dimensional array with a maximum size of 2n + 1.
• If the index of a node is i then left child will be at 2*i and the right child will be at
2*i+1.
• This representation appears to be good for complete binary trees and wasteful for many other
binary trees.
• In addition, the insertion or deletion of nodes from the middle of a tree requires the insertion of
many nodes to reflect the change in level number of these nodes
example
 2. Linked List Representation of Binary Tree
• The linked representation is the most
popular, efficient and frequently employed
representation of binary tree.
• In the linked list representation every node
is represented by data, pointer to left child,
pointer to right child.
In this linked list representation, a node has
the following structure...
 Binary Search Tree-
Binary Search Tree is a special kind of binary tree in which nodes are
arranged in a specific order.
• In a binary search tree (BST), each node contains-
• Only smaller values in its left sub tree
• Only larger values in its right sub tree
Advantages of Binary search tree

• Searching an element in the Binary search tree is easy as we always

have a hint that which subtree has the desired element.
• As compared to array and linked lists, insertion and deletion
operations are faster in BST.
BST Traversal-
• A binary search tree is traversed in exactly the same way a binary tree is
traversed.
• Preorder Traversal-
•  100 , 20 , 10 , 30 , 200 , 150 , 300
•  Inorder Traversal-
•  10 , 20 , 30 , 100 , 150 , 200 , 300
• It always comes in increasing order
•  Postorder Traversal-
•  10 , 30 , 20 , 150 , 300 , 200 , 100
Construction of Binary Search Tree using its traversal

The preorder traversal sequence of a binary search tree is-

30 , 20 , 10 , 15 , 25 , 23 , 39 , 35 , 42.
• Inorder Traversal : 10 , 15 , 20 , 23 , 25 , 30 , 35 , 39 , 42
Example 2
Example 3
Operations in a BST
• Searching
• Creation
• Insertion
• Deletion
Searching in Binary search tree
• Searching means to find or locate a specific element or node in a data structure.
In Binary search tree, searching a node is easy because elements in BST are
stored in a specific order. The steps of searching a node in Binary Search tree are
listed as follows -
• First, compare the element to be searched with the root element of the tree.
• If root is matched with the target element, then return the node's location.
• If it is not matched, then check whether the item is less than the root
element, if it is smaller than the root element, then move to the left subtree.
• If it is larger than the root element, then move to the right subtree.
• Repeat the above procedure recursively until the match is found.
• If the element is not found or not present in the tree, then return NULL.
Suppose we have to find node 20 from the below tree.
 Binary Search Tree Construction/Creation

• Construct a Binary Search Tree (BST) for the following sequence of

numbers- 50, 70, 60, 20, 90, 10, 40, 100
• When elements are given in a sequence,
• Always consider the first element as the root node.
• Consider the given elements and insert them in the BST one by one.
• Insert 50-
• Insert 70- As 70 > 50, so insert 70 to the right of 50.
60, 20, 90, 10, 40, 100

• Insert 60-

• Insert 20-

• Insert 90-
10, 40, 100
• Insert 10-

• Insert 40-

• Insert 100-
Problem 2: 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24
 Insertion in Binary Search tree
• A new key in BST is always inserted at the leaf. To insert an element in BST, we have
to start searching from the root node; if the node to be inserted is less than the
root node, then search for an empty location in the left subtree.
• Else, search for the empty location in the right subtree and insert the data.
• Insert in BST is similar to searching, as we always have to maintain the rule that the
left subtree is smaller than the root, and right subtree is larger than the root.
Deletion from BST (Binary Search Tree)
Deletion example 2
delete node 90
• delete the node 79
• delete node 45