Compiled by
Mhlanga L
PRESANTATION 8 OF 9
TREES
1. Explain the concept of a tree data structure.
2. Outline the properties of trees.
3. Explain binary tree representation, operations,
traversals (preorder, in-order and post-order).
4. Explain binary search trees and recursive binary
search trees.
5. Compare binary search trees and linear lists.
6. Apply binary search trees in evaluating
expressions and sorting.
✓ A tree is a nonlinear data structure, which is used
to represent hierarchical relationships (parent-
child relationship).
✓ Each node is connected by another node by
directed edges.
✓ A tree is recursively defined as a set of one or
more nodes where one node is designated as the
root of the tree and all the remaining nodes can
be partitioned into non-empty sets each of which
is a sub-tree of the root
✓ A tree where node A is the root node; nodes B, C, and D are children of the
root node and form sub-trees of the tree rooted at node A.
✓ Ancestor node - An ancestor of a node is any predecessor node on the
path from root to that node. The root node does not have any ancestors.
✓ Descendant node - A descendant node is any successor node on any path
from the node to a leaf node. Leaf nodes do not have any descendants.
Left-skewed bin tree Perfect bin tree
✓ Root: The root of the tree is the only node in the tree that has no
incoming edges. It is the top node of a tree.
✓ Node: It is a fundamental element of a tree. Each node has data and
two pointers that may point to null or its child’s.
✓ Edge: It is also a fundamental part of a tree, which is used to connect
two nodes.
✓ Path: A path is an ordered list of nodes that are connected by edges.
✓ Leaf: A leaf node is a node that has no children.
✓ Height of the tree: The height of a tree is the number of edges on
the longest path between the root and a leaf.
✓ The level of node: The level of a node is the number of edges on the
path from the root node to that node.
✓ In-degree/out-degree of a node: It is the number of edges arriving at
a node. The root node is the only node that has an in-degree equal to
zero. Similarly, out-degree of a node is the number of edges leaving
that node.
✓ Children: Nodes that have incoming edges from the same node to be said to be
the children of that node.
✓ Parent: Node is a parent of all the child nodes that are linked by outgoing edges.
✓ Sibling: Nodes in the tree that are children of the same parent are said to be
siblings’
✓ Ancestor: A node reachable by repeated moving from child to parent.
✓ A binary tree is a finite set of nodes that is either
empty or consist a root node and two disjoint
binary trees called the left subtree and the right
subtree.
✓ In other words, a binary tree is a non-linear data
structure in which each node has maximum of
two child nodes.
✓ The tree connections can be called as branches A
binary tree is a special case of an ordered tree,
where k is 2.
A binary tree is very similar to a tree in its structure and terminology.
The additional features with respect to binary tree are:
(1) A binary tree with n elements will have n–1 number of edges, where n>0.
(2) At level i a binary tree can have at most 2i–1 number of nodes, where i≥1.
(3) A binary tree of height h can have minimum h and maximum 2h–1 number
of nodes, here h≥0.
(4) For a binary tree with n elements, height is minimum ªlog2 (n+1)ºand
maximum n.
(5) In a binary tree the number of non-terminal nodes will be one less than
that of the number of terminal nodes.
The major differences between a tree and a binary tree are:
• A tree can never be empty whereas a binary tree can be empty with no
nodes.
• Th ere may be any number of subtrees for a node in a tree. There must be
either zero or one or two subtrees for a node in a binary tree.
• Th ere is no ordering of subtrees in a tree, but the ordering of left and right
subtrees of all nodes is clearly maintained in a binary tree.
A binary tree is a type tree in which each node has
at most two children (0, 1 or 2), which are referred
to as the left child and the right child.
Linked Representation of Binary Tree. Sequential or Array Representation of
Binary Tree.
LEFT [.] contains the location of the left
child of node 6. 6 contains the data at
the node 6. RIGHT [.] contains the
location of right child of node 6.
✓ The root element P is placed in the first position of the array, i.e. i=1 position.
✓ Its left child Q is placed in 2i=2*1=2nd position of the array.
✓ Its right child R is placed in 2i+1=2*1+1=2+1=3, 3rd position of the array.
✓ Now consider the element Q, as it is in the 2nd position of array, i=2, since it
does not have a left child, the 4th position of the array is left empty.
✓ Its right child S is placed in 2i+1=2*2+1=5th position of the array.
✓ Similarly, when S is considered, i=5, its left child is placed in 10th position and its
right child is placed in 11th position.
✓ For the elements that are missing in the binary tree, their corresponding
positions in the array are left empty.
Advantages of sequential representation:
The only advantage with this type of representation is that the direct access to
any node can be possible and finding the parent or left children of any
particular node is fast because of the random access.
Disadvantages of sequential representation:
1. The major disadvantage with this type of representation is wastage of
memory. For example in the skewed tree half of the array is unutilized.
2. In this type of representation the maximum depth of the tree has to be
fixed. Because we have decide the array size. If we choose the array size
quite larger than the depth of the tree, then it will be wastage of the
memory. And if we choose array size lesser than the depth of the tree
then we will be unable to represent some part of the tree.
3. The insertions and deletion of any node in the tree will be costlier as
other nodes has to be adjusted at appropriate positions so that the
meaning of binary tree can be preserved. As these drawbacks are there
with this sequential type of representation, we will search for more
flexible representation. So instead of array we will make use of linked list
to represent the tree.
✓ The linked representation is an efficient and advantageous
method to represent a binary tree over arrays.
✓ The node structure contains three fields, a DATA fi eld and two
pointers, LCHILD and RCHILD to point to the left and right
children of nodes, respectively.
✓ By using a pointer to the root node the tree can be accessed.
Advantages of linked representation:
1. This representation is superior to our array representation as
there is no wastage of memory. And so there is no need to
have prior knowledge of depth of the tree. Using dynamic
memory concept one can create as much memory(nodes) as
required. By chance if some nodes are unutilized one can
delete the nodes by making the address free.
2. Insertions and deletions which are the most common
operations can be done without moving the nodes.
Disadvantages of linked representation:
1. This representation does not provide direct access to a node
and special algorithms are required.
2. This representation needs additional space in each node for
storing the left and right subtrees.
1) The maximum number of nodes at level ‘l’ of a
binary tree is 2l-1 .
2) Maximum number of nodes in a binary tree of
height ‘h’ is 2h – 1.
3) In a Binary Tree with N nodes, minimum possible
height or minimum number of levels is ⌈ Log2(N+1) ⌉
4) A Binary Tree with L leaves has at least ⌈ Log2L ⌉ + 1
levels
5) In Binary tree where every node has 0 or 2 children,
number of leaf nodes is always one more than
nodes with two children.
• Search: Search is an operation that is performed on a binary
tree to find a given key in the tree. If it is found then the search
is successful and if it is not found it is an unsuccessful search.
• Insert: Insertion is an operation that is performed on a binary
tree to include an element in an existing binary tree. A new
element can be inserted at any position in a binary tree. To insert
an element along with the element the node or element to
which the new element is inserted a child must be specified. Th e
new element either to be inserted as a left child or as a right
child can also be mentioned.
• Delete: Deletion is an operation that is performed on a binary
tree to remove an element from a nonempty binary tree.
• Merge: Merge is an operation that is performed on a binary
tree to merge or combine two binary trees into one.
• Display: Display is an operation that is performed on a binary
tree to output or show the elements of a binary tree.
✓ The very first insertion 1. If root is NULL
creates the tree. 2. then create root node
✓ Afterwards, whenever an 3. return
element is to be inserted, 4. If root exists then
first locate its proper 5. compare the data with
location. node.data
✓ Start searching from the root 6. while until insertion position
node, then if the data is less is located
than the key value, search for 7. If data is greater than
the empty location in the left node.data
subtree and insert the data. 8. goto right subtree
✓ Otherwise, search for the 9. else
empty location in the right 10. goto left subtree
subtree and insert the data. 11. endwhile
12. insert data
13. end If
✓ Whenever an element is 1. If root.data is equal to
to be searched, start search.data
searching from the root 2. return root
node, then if the data is 3. else
less than the key value, 4. while data not found
search for the element in 5. If data is greater than
the left subtree. node.data
✓ Otherwise, search for the 6. goto right subtree
element in the right 7. else
subtree. 8. goto left subtree
✓ Follow the same 9. If data found return node
algorithm for each node. 10. endwhile
11. return data not found
12. end if
✓ In a complete binary tree, every level except the last one is completely
filled.
✓ All nodes in the left are filled first, then the right one.
✓ A complete binary tree is a binary tree therefore satisfies two properties.
First, in a complete binary tree, every level, except possibly the last, is
completely filled. Second, all nodes appear as far left as possible.
✓ A binary heap is an example of a complete binary tree.
A binary tree T is said to be
complete binary tree if:
1. All its levels, except
possibly except
possibly the last, have
the maximum number
of nodes and
2. All the nodes at the
last level appears as
far left as possible.
✓ When every non leaf node in a binary tree is
filled with left and right subtrees, the tree is
called a strictly binary tree.
✓ The full binary tree is a binary tree in which each
node has exactly zero or two children.
✓ The binary tree that is extended with zero (no nodes) or left or right
node or both the nodes is called an extended binary tree or a 2- tree.
✓ The extended binary tree is shown in figure above.
✓ The extended nodes are indicated by square box.
✓ Maximum nodes in the binary tree have one child (nodes) shown at
either left or right by adding one or more children, the tree can be
extended.
✓ The extended binary tree is very useful for representation of
algebraic expressions.
✓ The left and right child nodes denote operands and parent node
indicates operator.
✓ To convert a binary tree into
an extended tree, every
empty sub-tree is replaced by
a new node.
✓ The original nodes in the tree
are the internal nodes, and
the new nodes added are
called the external nodes.
✓ The perfect binary tree is a type of full binary
tree in which each non-leaf node has exactly two
child nodes.
✓ All leaf nodes have identical path length and all
possible node slots are occupied
A Binary Tree is full binary
tree if and only if:
1. Each non- leaf node has
exactly two child
nodes.
2. All leaf nodes are at the
same level.
✓ Tree traversal is the process of visiting each node in
the tree exactly once.
✓ Visiting each node in a graph should be done in a
systematic manner.
✓ If search result in a visit to all the vertices, it is called
a traversal.
✓ There are basically three traversal techniques for a
binary tree that are,
1. • Preorder traversal
2. • In-order traversal
3. • Post-order traversal
To traverse a binary tree in preorder, following operations are carried
out:
1. Visit the root.
2. Traverse the left sub tree of root.
3. Traverse the right sub tree of root.
Note: Preorder traversal is also known as NLR traversal.
Traversal is a process of visiting each node of a tree. In The pre-order traversal is:
Pre-Order Traversal parent is visited/traversed first,
then left child and right child. Pre-Order traversal is a ABDEHCFGIKJ
type of depth-first traversal.
✓ Pre-order traversal is also called as depth-first traversal.
✓ In this algorithm, the left sub-tree is always traversed before the
right sub-tree.
✓ The word ‘pre’ in the pre-order specifies that the root node is
accessed prior to any other nodes in the left and right sub-trees.
✓ Pre-order algorithm is also known as the NLR traversal algorithm
(Node-Left-Right).
To traverse a binary tree in in-order traversal, following operations are
carried out:
1. Traverse the left most sub tree.
2. Visit the root.
3. Traverse the right most sub tree.
Note: In-order traversal is also known as LNR traversal.
✓ In In-Order Traversal left child is visited/traversed
first, then the parent and last right child In-Order The in-order traversal is :
traversal is a type of depth-first traversal.
✓ The output of In-Order traversal of BST is a sorted DBHEAFCKIGJ
list.
✓ In-order traversal is also called as symmetric traversal.
✓ In this algorithm, the left sub-tree is always traversed
before the root node and the right sub-tree.
✓ The word ‘in’ in the in-order specifies that the root node
is accessed in between the left and the right sub-trees.
✓ In-order algorithm is also known as the LNR traversal
algorithm (Left-Node-Right).
To traverse a binary tree in post-order traversal, following operations
are carried out:
1. Traverse the left sub tree of root.
2. Traverse the right sub tree of root.
3. Visit the root.
Note: Post-order traversal is also known as LRN traversal.
In Post-Order Traversal left child is
visited/traversed first, then right child and last
The post-order traversal
parent Post-Order traversal is a type of depth- is:DHEBFKIJGCA
first traversal.
✓ In this algorithm, the left sub-tree is always traversed
before the right sub-tree and the root node.
✓ The word ‘post’ in the post-order specifies that the root
node is accessed after the left and the right sub-trees.
✓ Post-order algorithm is also known as the LRN traversal
algorithm (Left-Right-Node).
✓ Level order traversal or Breadth First traversal of a tree is
done using a queue.
✓ At the start, the root node pointer is added to queue.
✓ The traversal of tree happens until its queue is empty.
✓ When we traverse the tree, we first remove an element from
the queue, print the value stored in that node and then its left
child and right child will be added to the queue.
A binary search tree (BST) is a binary tree on which nodes are ordered in
the following way:
· The key in the left subtree is less than the key in its parent node.
· The key in the right subtree is greater the key in its parent node.
· No duplicate key allowed.
Note: there can be two separate key and value fields in the tree node. But
for simplicity, we are considering value as the key. All problems in the
binary search tree are solved using this supposition that the value in the
node is key for the tree.
Note: Since binary search tree is a binary tree to all the above algorithm of
a binary tree are applicable to a binary search tree.
✓ Binary search trees also speed up the insertion and deletion operations.
✓ The tree has a speed advantage when the data in the structure changes rapidly.
✓ Binary search trees are considered to be efficient data structures especially when compared
with sorted linear arrays and linked lists.
✓ In a sorted array, searching can be done in O(log2n) time, but insertions and deletions are
quite expensive.
✓ In contrast, inserting and deleting elements in a linked list is easier, but searching for an
element is done in O(n) time.
✓ However, in the worst case, a binary search tree will take O(n) time to search for an
element.
✓ The root node is 39. The left sub-tree of the
root node consists of nodes 9, 10, 18, 19, 21,
27, 28, 29, and 36.
✓ All these nodes have smaller values than
the root node. The right sub-tree of the
root node consists of nodes 40, 45, 54, 59,
60, and 65.
✓ Recursively, each of the sub-trees also
obeys the binary search tree constraint.
✓ For example, in the left sub-tree of the
root node, 27 is the root and all elements
in its left sub-tree (9, 10, 18, 19, 21) are
smaller than 27, while all nodes in its right
sub-tree (28, 29, and 36) are greater than
the root node’s value.
✓ Since the elements in the array are in sorted order and we want to create a binary
search tree in which left subtree nodes are having values less than the current node
and right subtree nodes have value greater than the value of the current node.
✓ We have to find the middle node to create a current node and send the rest of the
array to construct left and right subtree.
✓ Eg Create a binary search tree using the following data elements: 45, 39, 56, 12, 34, 78,
32, 10, 89, 54, 67, and 81.
Inserting a New Node in a Binary Search Deleting a Node from a Binary Search
Tree Tree
✓ The insert function is used to add a new node ✓ The delete function deletes a node
with a given value at the correct position in the
binary search tree.
from the binary search tree.
✓ Adding the node at the correct position means ✓ However, utmost care should be
that the new node should not violate the taken that the properties of the
properties of the binary search tree. binary search tree are not violated
✓ The initial code for the insert function is similar
to the search function. and nodes are not lost in the process.
✓ This is because we first find the correct position 1. Case 1: Deleting a Node that has No
where the insertion has to be done and then Children
add the node at that position.
✓ The insertion function changes the structure of
2. Case 2: Deleting a Node with One
the tree. Child
✓ Therefore, when the insert function is called 3. Case 3: Deleting a Node with Two
recursively, the function should return the new Children
tree pointer.
✓ The insert function requires time proportional
to the height of the tree in the worst case. It
takes O(log n) time to execute in the average
case and O(n) time in the worst case.
✓ Binary Search tree exhibits a special behavior. A
node's left child must have value less than its
parent's value and node's right child must have
value greater than it's parent value.
✓ An optimal binary search tree (BST), is a binary
search tree which provides the smallest possible
search time (or expected search time) for a given
sequence of accesses (or access probabilities).
1. Trees are used to store simple as well as complex data. Here simple
means an integer value, character value and complex data means a
structure or a record.
2. Trees are often used for implementing other types of data structures
like hash tables, sets, and maps.
3. A self-balancing tree, Red-black tree is used in kernel scheduling, to
preempt massively multiprocessor computer operating system use.
4. Another variation of tree, B-trees are prominently used to store tree
structures on disc. They are used to index a large number of records.
5. B-trees are also used for secondary indexes in databases, where the
index facilitates a select operation to answer some range criteria.
6. Trees are an important data structure used for compiler construction.
7. Trees are also used in database design.
8. Trees are used in file system directories.
9. Trees are also widely used for information storage and retrieval in
symbol tables.
✓ The leaves of an expression tree are operands,
such as constants or variable names, and the
other nodes contain operators.
Given an expression, Exp = ((a + b) –
(c * d)) % ((e ^f) / (g – h)), construct
Expression tree for (a +
the corresponding binary tree. b * c) + ((d * e+f) * g)
✓ Traversing an expression tree being a binary tree is the
same as the traversal of a binary tree.
✓ In-order traversal of an expression tree gives infix
notation, preorder traversal gives prefix notation and
post-order traversal gives postfix notation of an
expression.
Trees are so useful and frequently used, because
they have some very serious advantages:
1. Trees reflect structural relationships in the data
2. Trees are used to represent hierarchies
3. Trees provide an efficient insertion and
searching
4. Trees are very flexible data, allowing to move
sub trees around with minimum effort
