Department of Computer Science and Engineering (CSE)

UNIVERSITY INSTITUTE OF
ENGINEERING
COMPUTER SCIENCE ENGINEERING
Bachelor of Engineering
Design and Analysis of
Algorithms(CSH-311/ITH-311)

Trees (BST, B Tree,)(CO2)

Topic: Trees DISCOVER . LEARN . EMPOWER

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Learning Objectives & Outcomes

Objective:
• To understand the meaning of Tree
• To Study its Hierarchical Structure .
• To analyze its Parent and Child node structure.

Outcome:
• Student will understand
 Tree and operations performed on tree
 Different Tree Types

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

What is tree??

• A tree is a finite nonempty Computers”R”Us

set of elements.

• It is an abstract model of a
hierarchical structure. Sales Manufacturing
R&D

• consists of nodes with a

parent-child relation. US
International
Laptops
Desktops

• Applications:
– Organization charts
Europe Asia Canada
– File systems
– Programming environments

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Terminologies
• Root: node without parent (A)

• Siblings: nodes share the same parent

• Internal node: node with at least one child (A, B, C, F)

• External node (leaf ): node without children (E, I, J, K, G,

H, D)

• Ancestors of a node: parent, grandparent, grand-

grandparent, etc.

• Descendant of a node: child, grandchild, grand-

grandchild, etc.
University Institute of Engineering (UIE)
 Department of Computer Science and Engineering (CSE)

Terminologies (Contd…)
• Depth of a node: number of ancestors.

• Height of a tree: maximum depth of any node.

• Degree of a node: the number of its children.

• Degree of a tree: the maximum number of its node.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Tree representation

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Left child, right child and siblings

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Tree traversal

• Two main methods:

– Preorder
– Postorder

• Recursive definition

• Preorder:
– visit the root
– traverse in preorder the children (subtrees)

• Postorder
– traverse in postorder the children (subtrees)
– visit the root

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Binary tree

• A binary tree is a tree with the following properties:

– Each internal node has at most two children (degree of two)

– The children of a node are an ordered pair

• We call the children of an internal node left child and

right child

• Alternative recursive definition: a binary tree is either

– a tree consisting of a single node, OR

– a tree whose root has an ordered pair of children, each of which is
a binary tree

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Examples of binary tree

Skewed Binary Tree Complete Binary Tree

A A A

B B
B C

D E F G
D

E H I

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Full binary tree

• A full binary tree of a given height k has 2k+1–1 nodes.

Height 3 full binary tree.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Full binary tree (Contd..)

• Label the nodes 1 through 2k+1 – 1.
• Label by levels from top to bottom.
• Within a level, label from left to right.
• Parent of node i is node i / 2, unless i = 1.
• Node 1 is the root and has no parent.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Complete binary tree

• A labeled binary tree containing the labels 1 to

n with root 1, branches leading to nodes
labeled 2 and 3, branches from these leading to
4, 5 and 6, 7, respectively, and so on.

• A binary tree with n nodes and level k is

complete off its nodes correspond to the nodes
numbered from 1 to n in the full binary tree of
level k.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Binary Tree

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Binary tree traversal

• Let l, R, and r stand for moving left, visiting the

node, and moving right.

• There are six possible combinations of traversal lRr,

lrR, Rlr, Rrl, rRl, rlR.

• Adopt convention that we traverse left before right,

only 3 traversals remain

– lRr, lrR, Rlr

– inorder, postorder, preorder

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

AVL Tree
• AVL tree is a self-balancing Binary Search Tree (BST)
where the difference between heights of left and right
subtrees cannot be more than one for all nodes.
• Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert,
delete.. etc) take O(h) time where h is the height of the
BST. The cost of these operations may become O(n) for a
skewed Binary tree. If we make sure that height of the
tree remains O(Logn) after every insertion and deletion,
then we can guarantee an upper bound of O(Logn) for all
these operations

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Example

The above tree is AVL because differences between heights

of left and right subtrees for every node is less than or
equal to 1.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

B Tree

• All leaves are at the same level.

• A B-Tree is defined by the term minimum degree ‘t’. The value
of t depends upon disk block size.
• Every node except root must contain at least t-1 keys. The root
may contain minimum 1 key.
• All nodes (including root) may contain at most 2t – 1 keys.
• Number of children of a node is equal to the number of keys in
it plus 1.
• All keys of a node are sorted in increasing order. The child
between two keys k1 and k2 contains all keys in the range
from k1 and k2.
• B-Tree grows and shrinks from the root which is unlike Binary
Search Tree. Binary Search Trees grow downward and also
shrink from downward.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Red black tree

• Red-Black Tree is a self-balancing Binary Search Tree

(BST) where every node follows following rules:
1) Every node has a color either red or black.
2) Root of tree is always black.
3) There are no two adjacent red nodes (A red node cannot
have a red parent or red child).
4) Every path from a node (including root) to any of its
descendant NULL node has the same number of black
nodes.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Why Red black tree?

Most of the BST operations (e.g., search, max, min, insert,

delete.. etc) take O(h) time where h is the height of the BST.
The cost of these operations may become O(n) for a skewed
Binary tree. If we make sure that height of the tree remains
O(Logn) after every insertion and deletion, then we can
guarantee an upper bound of O(Logn) for all these
operations. The height of a Red-Black tree is always
O(Logn) where n is the number of nodes in the tree.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

REFERENCES
Text books:
•Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, Prentice Hall of
India, 3rd edition 2012. problem, Graph coloring.
•Horowitz, Sahni and Rajasekaran, “Fundamentals of ComputerAlgorithms”,
University Press (India), 2nd edition

Websites:
1.https://www.tutorialride.com/data-structures/trees-in-data-structure.htm
2.https://www.geeksforgeeks.org/avl-tree-set-1-insertion/

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Summary
Introduction to Trees
• Basic terms

Types of Trees
• Binary tree
• B tree
• Balanced trees

University Institute of Engineering (UIE)

THANK YOU

University Institute of Engineering (UIE)