Trees
Hierarchies
Many ways to represent tree-like
information:
A I. A
1.B
B C
a. D
i. E
D G
b. F
F
2.C
E
a. G A
linked
outlines E
hierarchy
, D B
indentati G C F
(((E):D), F):B, ons
(G):C):Alabeled
nested,
nested
parenthesis
sets
Definition
A tree T is defined as a finite set of
one or more nodes such that:
a) There is a specially designed node called the root,
b) Remaining nodes are partitioned in to n (n>0) disjoint
sets T1, T2,…, Tn , where each Ti is a tree. T1, T2,…, Tn are
called sub trees of the root.
A
B C D T3
T1
G H I J
E F
L M
T2
K
Applications of Tree Data Structure
• Trees are used to store simple as well as complex
data. Here simple means an int value, char value
and complex data (structure).
• Trees are often used for implementing other types of
data structures like hash tables, sets, and maps.
• A self-balancing tree, Red-black tree is used in
kernel scheduling to preempt massively multi-
processor computer operating system use.
• Another variation of tree, B-trees are used to store
tree structures on disc. They are used to index a
large number of records.
Applications of Tree Data
Structure(Cont.)
• B-trees are also used for secondary indexes in
databases, where the index facilitates a select
operation to answer some range criteria.
• Trees are used for compiler construction.
• Trees are also used in database design.
• Trees are used in file system directories.
• Trees are also widely used for information storage
and retrieval in symbol tables.
Terminology
• r is the parent of its children r1,
r2, ..., rk.
• r1, r2, ..., rk are
siblings.
• root = distinguished node, usually ro
drawn at top. Has no parent. ot path
internal from
• If all children of a node are Λ, the root to
node
node is a leaf. Otherwise, the node w
is a internal node. pare
u nt
• A path in the tree is a sequence of of w
nodes u1, u2, ..., um such that each
children of u w
of the edges (u, ui+1) exists.
(they are
leav
• A node u is an ancestor of v if siblings)
es
there is a path from u to v.
• A node u is a descendant of v if
there is a path from v to u.
Height & Depth
• The height of node u is the length of the longest path from
u to a leaf.
• The depth of node u is the length of the path from the
root to u.
• Height of the tree = maximum depth of its
nodes.
• A level is the set of all nodes at the
same depth.
Depth = 3 Numbers
0 in nodes
Depth = 1 2 give
1 heights
Depth = 0 0 0 1
2
Depth = 0 0
3 0
Subtrees, forests, and graphs
• A subtree rooted at u is the tree formed from
u and all its descendants.
• A forest is a (possibly empty) set of trees.
The set of subtrees rooted at the children of
r form a forest.
• As we’ve defined them, trees are not a
special case of graphs:
- Our trees are oriented (there is a root which
implicitly defines directions on the edges).
- A free tree is a connected graph with no
cycles.
Basic Properties
• Every node except the root has exactly one
parent.
• A tree with n nodes has n-1 edges
(every node except the root has an
edge to its parent).
• There is exactly one path from the root to
each node. (Suppose there were 2 paths,
then some node along the 2 paths would
have 2 parents.)
Binary Trees – Definition
• An ordered tree is a tree for which the
order of the children of each node is
considered important.
r r
r1
r2
r3 r4 ≠ r4 r3 r1 r2
• A binary tree is an ordered tree such that
each node has ≤ 2 children.
• Call these two children the left and right
children.
Properties of binary tree
In any binary tree, the maximum no. of nodes on level l
is 2l , where l>=0.
Maximum no. of nodes possible in a binary tree of
height h is 2h+1-1.
Minimum no. of nodes possible in a binary tree of height
h is h+1.
For strict binary tree, if n is the no. of nodes and e is the
no. of edges, then, n= e+1
Example Binary
Trees
The edge
cases:
Singl Empt
Only Only
e y
left right
node Binar
child child
y
Tree
Small binary
tree:
Full and Complete Binary
Trees
• If every node has either 0 or 2 children, a binary tree is
called full.
• If the lowest d-1 levels of a binary tree of height d are
filled and level d is partially filled from left to right,
the tree is called complete.
• If all d levels of a height-d binary tree are filled, the
tree is called
perfect.
ful comple perfe
l te ct
Extended Binary
Trees
Replace each
missing child with
external node
Do you need a
special flag to tell
which nodes are
Binary Extended binary
external?
tree tree
Every internal node has exactly 2 children.
Every leaf (external node) has exactly 0 children.
Each external node corresponds to one Λ in the
original tree – let’s us distinguish different instances
of Λ.
Representing General Trees with Binary
Trees
A A
B C D B C D
E E
E F G E F G
H H
General K-ary Representatio
Tree n as Binary
Tree
How would you implement an ordered general tree using a
binary tree?
Ans: First Child/ Next Sibling Representation
# of External Nodes in Extended
Binary Trees
Thm. An extended binary tree with n internal nodes has
n+1 external nodes.
Proof. By induction on n.
X(n) := number of external nodes in binary tree with
n internal nodes.
Base case: X(0) = 1 = n + 1.
Induction step: Suppose theorem is true for
all i < n. Because n ≥ 1, we have:
Extended binary tree
X(n) = X(k) + X(n-k-1)
= k+1 + n-k-1 + 1
= n+ 1
☐
k nodes n-k-1
(for some 0 nodes Related to Thm
≤ k < n) 5.2 in your
Alternative Proof
Thm. An extended binary tree with n internal nodes has n+1
external nodes.
Proof. Every node has 2 children pointers, for a total of 2n
pointers.
Every node except the root has a parent, for a total of n - 1 nodes
with parents. These n - 1 parented nodes are all children, and each
takes up 1 child pointer.
(pointers) - (used child pointers) = (unused child
pointers) 2n - (n-1) = n + 1
Thus, there are n + 1 null pointers.
Every null pointer corresponds to one external node by
construction. ☐
# Nodes in a Perfect Tree of Height h
Thm. A perfect tree of height h has 2h+1 - 1
nodes.
Proof. By induction on h.
Let N(h) be number of nodes in a perfect tree of height h.
Base case: when h = 0, tree is a single node. N(0) =
1 = 20+1 - 1. Induction step: Assume N(i) = 2i+1 - 1 for
0 ≤ i < h.
A perfect binary tree of height h consists of 2 perfect
binary trees of height h-1 plus the root:
N(h)
= 2 × N(h - 1) + 1
= 2 × (2h-1+1 - 1) + 1
= 2 × 2h - 2 + 1
Full Binary Tree Theorem
Thm. In a non-empty, full binary tree, the number of internal
nodes is always 1 less than the number of leaves.
Proof. By induction on n.
L(n) := number of leaves in a non-empty, full tree of n internal
nodes.
Base case: L(0) = 1 = n + 1.
Induction step: Assume L(i) = i + 1 for i < n.
Given T with n internal nodes, remove two sibling leaves.
T’ has n-1 internal nodes, and by induction hypothesis, L(n-1)
= n leaves. Replace removed leaves to return to tree T.
Turns a leaf into an internal node, adds two new leaves.
Thus: L(n) = n + 2 - 1 = n + 1.
Thm 5.1 in your book.
Representation of binary tree
Implicit & Explicit representation
Implicit representation
Sequential / Linear representation, using arrays.
Explicit representation
Linked representation, using pointers.
Sequential representation(Using 1D Array )
• This representation is static.
• Block of memory for an array is allocated, before
storing the actual tree.
• Once the memory is allocated, the size of the tree will
be fixed.
• Nodes are stored level by level, starting from the
zeroth level.
• Root node is stored in the starting memory location,
as the first element of the array.
• Following rules are applied for storing the elements
of binary tree in the 1D array.
• The root R of T is stored in location 0.
• For any node with index i in range 0 =< i < n:
• left(i): 2i+1
• right(i): (2i + 2)
• parent(i): (i-1)/2
Array Implementation for Complete
Binary Trees A
0
B 1 C
2
D 3 E F G
Mappin
g
of nodes
H I J K L M
to
integers
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12 13
14
Sequential representation- Merits and
Demerits
Merits
• Random and Faster Access-Any node can be
accessed from any other node by calculating the
index.
• Space -Here, data are stored simply without any
pointers to their successor or predecessor.
• Easy -Inserting a new node and deletion of an
existing node is easy.
Demerits-
• Wastage of Space- If binary tree becomes
unbalanced(skewed) there will be lots of unused
array cells
• Limited size- Can store fixed size of binary tree
Linked Representation of Binary Trees
• In computer’s memory, a binary tree can be
maintained either using a linked representation or
using sequential representation.
• In linked representation of binary tree, every node
will have three parts: the data element, a pointer to
the left node and a pointer to the right node. So in C,
the binary tree is built with a node type given as
below.
struct node
{
struct node* lc;
int data;
struct node* rc;
Linked list representation: Example
4
2 7
1 3 9
4
1 1 8
2 x 7
x 1 3 x 9 x
x 1 x x 1 x x 8 x
Operations on Binary tree
• Traversal
• Insertion of a node
• Deletion of a node
• Searching
• Height of a tree
• Depth of a node
• Number of nodes in tree