Trees

thi
s

i tre
a
s e

* Trees 1
What is a Tree
• In computer science,
Computers”R”
a tree is an abstract Us
model of a
hierarchical structure
Sale Manufacturi R&
• A tree consists of s ng D
nodes with a parent-
child relationship U Internation Lapto Deskto
• Applications: S al ps ps
• Organization charts
• File systems Europ Asi Canad
• Programming e a a
environments

* Trees 2
What is a Tree
• A connected acyclic graph is a tree.

• A tree T is a set of nodes in a parent-child

• A tree cannot be empty, since it must have at

* Trees 3
Tree Terminology
• Root: node without parent (A) • Subtree: tree consisting
• Internal node: node with at of a node and its
least one child (A, B, C, F) descendants
• External node (Leaf ): node A
without children (E, I, J, K, G, H,
D)
• Ancestors of a node: parent,
B C D
grandparent, grand-
grandparent, etc.
• Descendants of a node: child,
grandchild, grand-grandchild, E F G H
etc.
• Depth of a node: number of
ancestors, excluding the node
itself I J K subtr
• Height of a tree: maximum ee
depth of any node (3)
• Siblings: two nodes that are
* children of the same parent Trees 4
Depth and Height
• The depth of a node v can be recursively defined as
follows
• If v is the root, then the depth of v is 0.
• Otherwise, the depth of v is one plus the depth of
the parent of v
Algorithm depth(T, v)
if T.isRoot(v) then
return 0
else
return 1 + depth(T, T.parent(v))
Running time: O(1 + dv), dv is depth of v in T
In worst case O(n), n is the number of nodes in T
* Trees 5
Depth and Height
• The height of a node v can be recursively defined as
follows
• If v is a leaf node, then the height of v is 0.
• Otherwise, the height of v is one plus the
maximum height of a child of v
The height of a tree T is the height of the root of T

The height of a tree T is equal to the maximum

* Trees 6
Depth and Height
Algorithm height1(T)
h=0
for each v εT.positions(v) do
if T.isExternal(v) then
h = max(h, depth(T, v))
return h

Running time: O(n + Σv ε E (1 + dv)), where dv is depth of v in

* Trees 7
Depth and Height
Algorithm height2(T, v)
if T.isExternal(v) then
return 0
else
h=0
for each w ε T.children(v) do
h = max(h, height2(T, w))
return 1 + h
Running time: O(Σv ε T (1 + cv)), where cv is the number of
children of v in T
Since Σv ε T cv = n - 1, we have O(Σv ε T (1 + cv)) = O(n).
• The height of tree T is obtained by calling
* height2(T, r). Trees 8
Ordered Trees
• A tree is ordered if there is a linear ordering
defined for each child of each node.
• A binary tree is an ordered tree in which every
node has at most two children.
• If each node of a tree has either zero or two
children, the tree is called a proper (strictly)
binary tree.

* Trees 9
Traversal of Trees
• A traversal of a tree T is a systematic way of
visiting all the nodes of T
• Traversing a tree involves visiting the root and
traversing its subtrees
• There are the following traversal methods:
• Preorder Traversal
• Postorder Traversal
• Inorder Traversal (of a binary tree)

* Trees 10
Preorder Traversal
• In a preorder traversal, a Algorithm preOrder(v)
node is visited before its
descendants visit(v)
for each child w of v
• If a tree is ordered, then the
subtrees are traversed preorder (w)
according to the order1of A
the children
2 9
B
5 C D

3 4 6 7 8
E F I G H

Preorder: ABEFCIGHD
* Trees 11
Postorder Traversal
• In a postorder traversal, Algorithm postOrder(v)
a node is visited after its
for each child w of v
descendants
postOrder (w)
visit(v)

A 9
8
3
B 7 C D

1 2 6
4 5
E F I G H

Postorder: EFBIGHCDA
* Trees 12
Inorder Traversal
• In an inorder traversal Algorithm inOrder(v)
a node is visited after if isInternal (v)
its left subtree and inOrder (leftChild (v))
before its right subtree
visit(v)
if isInternal (v)
inOrder (rightChild (v))
6

2 8

1 4 7 9

3 5

* Trees 13
Inorder Traversal
Traversing a binary tree in inorder
1. Traverse the left subtree in inorder.
2. Visit the root.
3. Traverse the right subtree in
inorder.

Inorder: DGBAHEICF
* Trees 14
(Proper) Binary Tree
• A (proper) binary tree is a tree • Applications:
with the following properties: ■ arithmetic
• Each internal node has two expressions
children ■ decision processes
• The children of a node are an ■ searching
ordered pair A
• We call the children of an
internal node left child and
right child
B C
• Alternative recursive
definition: a (proper) binary
tree is either
D E F G
• a tree consisting of a single
node, or
• a tree whose root has an
ordered pair of children, each H I
of which is a binary tree
* Trees 15
Arithmetic Expression Tree
• Binary tree associated with an arithmetic
expression
• internal nodes: operators
• external nodes: operands
• Example: arithmetic expression tree for the
expression (2 × (a − 1) + (3 × b))
+
× ×

2 − 3 b

a 1

* Trees 16
Decision Tree
• Binary tree associated with a decision process
• internal nodes: questions with yes/no answer
• external nodes: decisions
• Example: dining decision
Want a fast
meal?
Ye N
s
How about o
On expense
coffee? account?
Ye N Ye N
Starbuc
s Spike’
o Al
s Café
o
ks s Forno Paragon
* Trees 17
Properties of Binary Trees
• Let T be a (proper) binary tree with n nodes, and let h
denote the height of T. Then T has the following
properties.
• The number of external (leaf) nodes in T is at least h+1
and at most 2h.
• The number of internal nodes in T is at least h and at
most 2h-1.
• The number of nodes in T is at least 2h+1 and at most
2h+1-1

* Trees 18
Properties of Binary Trees
• In a (proper) binary tree T, the number of external
nodes is 1 more than the number of internal nodes.

• Proof:
u

z w

* Trees 19
BinaryTree ADT
• The BinaryTree ADT extends the Tree
ADT, i.e., it inherits all the methods of
the Tree ADT
• Additional methods:
• position leftChild(v): returns the left child of
v
• position rightChild(v) : returns the right child
of v
• position sibling(v) : returns the sibling of
node v

* Trees 20
Linked Structure for Binary
Trees
• A node is
∅
represented by an
object storing
• Element
B
• Parent node
• Left child node
∅ ∅
• Right child node

B A D

A D ∅ ∅ ∅ ∅

C E C E

* Trees 21
Linked Structure for General
Trees
• A node is
represented by an ∅
object storing
• Element
• Parent node B
• Children
Container: ∅ ∅
Sequence of
children nodes
A D F
B

A D F

C E ∅ ∅
C E
* Trees 22
Print Arithmetic Expressions
• Specialization of an inorder Algorithm printExpression(v)
traversal
• print operand or operator
if hasLeft (v)
when visiting node print(“(’’)
• print “(“ before traversing
left subtree
inOrder (left(v))
• print “)“ after traversing print(v.element ())
right subtree
if hasRight (v)
+ inOrder (right(v))
print (“)’’)
× ×

2 − 3 b
((2 × (a − 1)) + (3
a 1 × b))
* Trees 23
Evaluate Arithmetic
Expressions
• Specialization of a Algorithm evalExpr(v)
postorder traversal if isExternal (v)
• recursive method return v.element ()
returning the value of a else
subtree x ← evalExpr(leftChild
• when visiting an (v))
internal node, combine y ← evalExpr(rightChild
the values of the (v))
subtrees + ◊ ← operator stored at v
return x ◊ y
× ×

2 − 3 2

5 1
* Trees 24