Trees

this

is a tree

* Trees 1
What is a Tree
• In computer science, a
tree is an abstract model Computers”R”Us
of a hierarchical
structure
• A tree consists of nodes Sales Manufacturing R&D
with a parent-child
relationship
• Applications: US International Laptops Desktops

• Organization charts
• File systems
Europe Asia Canada
• Programming
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 relationship
with the following properties:
• T has a special node r, called the root of T, with no

parent node
• Each node v of T, different from r, has a unique parent
node u

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

one node – the root.

* Trees 3
Tree Terminology
• Root: node without parent (A) • Subtree: tree consisting of
• Internal node: node with at least a node and its descendants
one child (A, B, C, F)
• External node (Leaf ): node without A
children (E, I, J, K, G, H, D)
• Ancestors of a node: parent,
grandparent, grand-grandparent, B C D
etc.
• Descendants of a node: child,
grandchild, grand-grandchild, etc.
• Depth of a node: number of E F G H
ancestors, excluding the node itself
• Height of a tree: maximum depth
of any node (3) subtr
•
I J K
Siblings: two nodes that are
children of the same parent ee

* 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 depth of a

leaf node of T

* 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 T,

E is the set of leaves in T
In worst case O(n2), n is the number of nodes in T

* 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 node Algorithm preOrder(v)
is visited before its descendants
visit(v)
• If a tree is ordered, then the for each child w of v
subtrees are traversed
according to the order of the preorder (w)
children 1 A

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, a Algorithm postOrder(v)
node is visited after its
for each child w of v
descendants
postOrder (w)
visit(v)

A 9

3 8
B 7 C D

1 2 6
4 5
E F I G H

Postorder: EFBIGHCDA
* Trees 12
Inorder Traversal
• In an inorder traversal a Algorithm inOrder(v)
node is visited after its if isInternal (v)
left subtree and before its inOrder (leftChild (v))
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 expressions
• Each internal node has two ■ decision processes
children
■ searching
• The children of a node are an
ordered pair A
• We call the children of an internal
node left child and right child
• Alternative recursive definition: a B C
(proper) binary tree is either
• a tree consisting of a single node,
or
D E F G
• a tree whose root has an ordered
pair of children, each of which is a
binary tree
H I

* 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?

Yes No

How about coffee? On expense account?

Yes No Yes No

Starbucks Spike’s Al Forno Café 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 2 h-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

• Parent node B
• 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 right print(v.element ())
subtree
if hasRight (v)
+ inOrder (right(v))
× ×
print (“)’’)

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

× ×

2 − 3 2

5 1
* Trees 24