TREE DATA STRUCTURE

 Binary Trees

 The simplest form of tree is a binary tree. A binary tree consists of

 a node (called the root node) and

 left and right sub-trees.

 Both the sub-trees are themselves binary trees.

TREE

 A tree is a nonlinear hierarchical data structure

that consists of nodes connected by edges
Terms to note
 Following are the important terms with respect to tree.
 Path − Path refers to the sequence of nodes along the edges of a tree.
 Root − The node at the top of the tree is called root. There is only one root per
tree and one path from the root node to any node.
 Parent − Any node except the root node has one edge upward to a node called
parent.
 Child − The node below a given node connected by its edge downward is called its
child node.
 Leaf − The node which does not have any child node is called the leaf node.
 Subtree − Subtree represents the descendants of a node.
 Visiting − Visiting refers to checking the value of a node when control is on the
node.
 Traversing − Traversing means passing through nodes in a specific order.
 Levels − Level of a node represents the generation of a node. If the root node is at
level 0, then its next child node is at level 1, its grandchild is at level 2, and so on.
 keys − Key represents a value of a node based on which a search operation is to be
carried out for a node.
Height and Depth of a tree
Types of Tree

1. Binary Tree
2. Binary Search Tree
3. AVL Tree
4. B-Tree
 In an ordered binary tree,
 The keys of all the nodes in the left sub-tree are less than that of the root,
 The keys of all the nodes in the right sub-tree are greater than that of the
root,
 The left and right sub-trees are themselves ordered binary trees.
Binary Search Tree Construction

 How to build & maintain binary trees? Algorithm

• Insertion  Perform search for value X
• Deletion

 Maintain key property (invariant)  Search will end at node Y (if X not in
• Smaller values in left subtree tree)
• Larger values in right subtree 
 Binary Search Tree – Insertion  If X < Y, insert new leaf X as new left
subtree for Y

 If X > Y, insert new leaf X as new right
subtree for Y
 Operator treated as the node/parent
 Operand – the leaf
 Binary Search Tree – Deletion
 Algorithm
1. Perform search for value X
2. If X is a leaf, delete X
3. Else // must delete internal node
 Replace with largest value Y on left subtree OR smallest value Z on right
subtree.
 Delete replacement value (Y or Z) from subtree
Observation
 O( log(n) ) operation for balanced tree
 Deletions may unbalance tree
Example 1
Example 2
Example 3
Tree traversal methods
Walk, pre-order and post-order
 Traversing a tree means visiting every node in the tree. You might, for instance,
want to add all the values in the tree or find the largest one. For all these
operations, you will need to visit each node of the tree.

 Stepping through the items of a tree, by means of the connections between

parents and children, is called walking the tree, and the action is a walk of the
tree.

 Often, an operation might be performed when a pointer arrives at a particular

node.

 pre-order walk : A walk in which each parent node is traversed before its children

 post-order walk: a walk in which the children are traversed before their
respective parents are traversed
post-order Traversal
 post-order walk: a walk in which the children are traversed before their
respective parents are traversed
pre-order traversal
 pre-order walk : A walk in which each parent node is traversed before its
children
Depth First Search or Level Order
Traversal
 BFS (Breadth-First Search) is a vertex-based method for determining the
shortest path in a graph.
In-order traversal :
 a walk in which a node's left subtree, then the node itself, and then finally its
right subtree are traversed
 (This last scenario, referring to exactly two subtrees, a left subtree and a
right subtree, assumes specifically a binary tree.)
Steps of Inorder traversal
 First, visit all the nodes in the left subtree
 Then the root node
 Visit all the nodes in the right subtree
In-order Traversal
Consider:
Show NLR, LNR, LRN and Level traversal
for the tree

Solution:
Contd…

 Pre-order traversal (pre-fix expression) NLR

 Inorder – traversal (infix expression) LNR
 Postorder – traversal (postfix expression) LRN
 INFIX AND POSTFIX EXPRESSION (REVERSE
POLISH NOTATION)

Infix Expression: conversion is as follows :

 Any expression in the standard form Scan the Infix string from left to
like "2*3-4/5" is an Infix(Inorder) right.
expression.
 Initialise an empty stack.
Postfix Expression:
 If the scannned character is an
 The Postfix(Postorder) form of the operand, add it to the Postfix string.
above expression is "23*45/-". If the scanned character is an
operator and if the stack is empty
 3 Infix to Postfix Conversion:
Push the character to stack.
 In normal algebra we use the infix
notation like a+b*c. The
corresponding postfix notation is
abc*+. The algorithm for the
 If the scanned character is an Operand and the stack is not empty, compare
the precedence of the character with the element on top of the stack
(topStack). If topStack has higher precedence over the scanned character Pop
the stack else Push the scanned character to stack. Repeat this step as long as
stack is not empty and topStack has precedence over the character.
Repeat this step till all the characters are scanned.
 (After all characters are scanned, we have to add any character that the
stack may have to the Postfix string.) If stack is not empty add topStack to
Postfix string and Pop the stack. Repeat this step as long as stack is not
empty.
 Return the Postfix string.
 Example

 Let us see how the above algorithm will be imlemented using an example.

Infix String : a+b*c-d

 Initially the Stack is empty and our Postfix string has no characters. Now, the

first character scanned is 'a'. 'a' is added to the Postfix string. The next

character scanned is '+'. It being an operator, it is pushed to the stack.

 Stack Postfix string

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which
is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*'
will be pushed to the stack.

Stack Postfix String

 ·
 If the scannned character is an operand, add it to the stack. If the scanned
character is an operator, there will be atleast two operands in the stack.

 If the scanned character is an Operator, then we store the top most element
of the stack(topStack) in a variable temp. Pop the stack. Now evaluate
topStack(Operator)temp. Let the result of this operation be retVal. Pop the
stack and Push retVal into the stack.

 Repeat this step till all the characters are scanned.

 After all characters are scanned, we will have only one element in the stack.
Return topStack.
 Evaluating Postfix use the infix notation
Expression like a+b*c. The
corresponding postfix
 Infix Expression:
notation is abc*+. The
 Any expression in the algorithm for the
standard form like "2*3- conversion is as
4/5" is an Infix(Inorder) follows:
expression.
 Scan the Postfix string
from left to right.
 Postfix Expression:  Initialise an empty
 The Postfix(Postorder) stack.
form of the above
expression is "23*45/-".
 Postfix Evaluation:
 In normal algebra we
REVIEW QUESTIONS

 Convert the expression a+b*c-d to Postfix expression

 Evaluate the postfix string: 123*+4-