Binary Trees

Overview
• Binary trees
• Full & Complete trees; Tree traversals; Balanced and sorted trees
• Binary search trees
• Searching; Inserting; Deleting
• Hashing
• Open address hashing; Insertion; Collisions; Searching records; Deleting
records
 Binary Trees
o A binary tree is a finite set of nodes that is either empty
or consists of a root and two disjoint binary trees called
the left sub-tree and the right sub-tree.
o Any tree can be transformed into binary tree;
• by left child-right child representation
o The left sub-tree and the right sub-tree are distinguished.
 Binary Trees Cont’d
• Every node in a binary tree can have at most two children.
• The two children of each node are called the left child and right child
corresponding to their positions.
• A node can have only a left child or only a right child or it can have no
children at all.
• Left child is always less than its parent, while right child is greater than
its parent.
Left child-right child tree representation
of a tree
A
B
E C

K F G D

L H

M I
J
 Parts of a binary tree
• A binary tree is composed of zero or more nodes
• A binary tree may be empty (contain no nodes)
• If not empty, a binary tree has a root node
• Every node in the binary tree is reachable from the root node by a unique
path
• A node with no left child and no right child is called a leaf.
• In some binary trees, only the leaves contain a value
 Left ≠ Right
• The following two binary trees are different:
A A

B B

• In the first binary tree, node A has a left child but no right child;
• In the second, node A has a right child but no left child
• Put another way: Left and right are not relative terms
 Tree Variations
• According to the definition of trees, a node can have any number
of children.
• A binary tree is restricted to only having 0, 1, or 2 children.
• A complete binary tree is one where all the levels are full with
exception to the last level and it is filled from left to right.
• A full binary tree is one where if a node has a child, then it has
two children.
 Full BT VS Complete BT
• A full binary tree is a binary tree where all the leaves are on the
same level and every non-leaf has two children.
• A complete binary tree of n nodes, is the binary tree made up of
the first n nodes of a canonically labeled full binary.
A A

B C B C
D E F G D E F G

H I H I J K L M N O

Complete binary tree Full binary tree of depth 4

 Examples
• Full binary trees

• Complete binary trees 1

1
2 3
2 3
1
4 5 6
4 2 3

4 5
 Canonical Labeling of Full Binary Trees

• Label the nodes from 1 to n from the top to the bottom, left to right
1
1 1 3
2
2 3

4 5 6 7
1 Relationships between labels
2 3 of children and parent:
5 6 7
4 i

2i 2i+1
8 9 10 11 12 13 14 15
 Size and depth
• The size of a binary tree is the number of nodes in it. a

• This tree has size 12

b c
• The depth of a node is its distance from the root.
• a is at depth zero d e f

• e is at depth 2 g h i j k
• The depth of a binary tree is the depth of its deepest node.
l
• This tree has depth 4
 Balanced binary trees
• A binary tree is balanced if every level above the lowest is “full”
(contains 2n nodes)
• In most applications, a reasonably balanced binary tree is
desirable. a
a b
b c c e
d e f g d f
g h
h i j i j
A balanced binary tree An unbalanced binary tree
 Sorted binary trees
• A binary tree is sorted if every node in the tree is larger than (or
equal to) its left descendants, and smaller than (or equal to) its
right descendants.
• Equal nodes can go either on the left or the right (but it has to be
consistent) 10

8 15

4 12 20

17
 Tree traversals
• To traverse (or walk) the binary tree is to visit each node in the binary tree
exactly once.
• Since a binary tree has three “parts,” there are six possible ways to traverse
the binary tree:
• root, left, right • root, right, left
• left, root, right • right, root, left
• left, right, root • right, left, root
• There are two very common traversals
• Breadth First or Depth First
 Breadth First
• In a breadth first traversal all of the nodes on a given
level are visited and then all of the nodes on the next
level are visited.
• Usually in a left to right fashion
• This is implemented with a queue.
 Depth First
• In a depth first traversal all the nodes on a branch are visited
before any others are visited
• There are three common depth first traversals
• In-order
• pre-order
• Post-order
 Tree traversals
In-order traversal
• In in-order, the root is visited in the middle.
• Here’s an in-order traversal to print out all the elements in the binary
tree:
Pre-order traversal
• Pre-order, the root is visited first.
• Here’s a pre-order traversal to print out all the elements in the binary
tree: In pre-order, the root is visited first.
• Here’s a pre-order traversal to print out all the elements in the binary
tree:
 Tree traversals
• Postorder traversal
• In postorder, the root is visited last
• Here’s a postorder traversal to print out all the elements in the binary
tree:
• The other traversals are the reverse of these three standard ones
• That is, the right sub-tree is traversed before the left sub-tree is traversed
• Reverse pre-order:- root, right sub-tree, left sub-tree
• Reverse inorder: - right sub-tree, root, left sub-tree
• Reverse postorder:- right subtree, left subtree, root
 Summary:
• In pre-order, the rootis visited before (pre)the sub-trees traversals
• In Inorder, the root is visited in-between left and right sub-tree traversal
• In Postorder, the root is visited after (post) the sub-trees traversals
pre-order Traversal: Inorder Traversal: Postorder Traversal:
1. Visit the root 1. Traverse left sub-tree 1. Traverse left sub-tree
2. Traverse left sub-tree 2. Visit the root 2. Traverse right sub-tree
3. Traverse right sub-tree 3. Traverse right sub-tree 3. Visit the root
 Traversals illustrations
• Assume: visiting a node is printing its label
1
• pre-order:
3 7
1 3 5 4 6 7 8 9 10 11 12
• Inorder: 5 8 9

4 5 6 3 1 8 7 9 11 10 12 10
4 6
• Postorder:
4 6 5 3 8 11 12 10 9 7 1 11 12
 Traversals illustrations
• Assume: visiting a node is printing its data 15

• pre-order: 15, 8, 2, 6, 3, 7,11, 10, 8 20

12, 14, 20, 27, 22, 30.

2 11 27
• Inorder: 2, 3, 6, 7, 8, 10, 11, 12,
14, 15, 20, 22, 27, 30. 6 10 12 22 30

• Postorder: 3, 7, 6, 2, 10, 14,12,

3 7 14
11, 8, 22, 30, 27, 20,15.
 Finding a Node
• To find a node given its key value, start from the root.
• If the key value is same as the node, then node is found.
• If key is greater than node, search the right sub-tree, else search the
left sub-tree.
• Continue till the node is found or the entire tree is traversed.
• Time required to find a node depends on how many levels down it is
situated
 Inserting a Node
• In order to build a tree you must be able to insert into the tree.
• To insert a node we must first find the place to insert it.
• Follow the path from the root to the appropriate node, which will be the
parent of the new node.
• When this parent is found, the new node is connected as its left or right
child, depending on whether the new node’s key is less or greater than
that of the parent.
 Finding Maximum and Minimum Values

• For the minimum,

• Go to the left child of the root and keep going to the left child until you come
to a leaf node.
• This node is the minimum.
• For the maximum,
• Go to the right child of the root and keep going to the right child until you
come to a leaf node. This node is the maximum.
 Deleting a Node
• Start by finding the node you want to delete.
• Then there are three cases to consider:
• The node to be deleted is a leaf
• The node to be deleted has one child
• The node to be deleted has two children
• Deletion poses a bigger problem
• When we delete we normally have two choices
• Deletion by merging
• Deletion by copying
 Deleting a Node

Deletion cases: Leaf Node

• To delete a leaf node, simply change the appropriate child field in
the node’s parent to point to null, instead of to the node.
• The node still exists, but is no longer a part of the tree.
 Deleting a Node
Deletion: One Child
• The node to be deleted in this case has only two connections: to
its parent and to its only child.
• Connect the child of the node to the node’s parent, thus cutting
off the connection between the node and its child, and between
the node and its parent.
 Deleting a Node
Deletion: Two Children
• To delete a node with two children, replace the node with its inorder
successor.
• For each node, the node with the next-highest key (to the deleted node)
in the sub-tree is called its inorder successor.
• To find the successor,
• start with the original (deleted) node’s right child.
• Then go to this node’s left child and then to its left child and so on, following
down the path of left children.
• The last left child in this path is the successor of the original node.
 Deletion by Merging
• Deletion by merging takes two sub-trees and merges them
together into one tree
• The idea is you have a node N to delete
• N can have two children
• So you find the smallest element in N’s left sub-tree
• You then take N’s right sub-tree and merge it to the bottom of
the left sub-tree.
• The root of the left sub-tree replaces N.
 Deletion by copying
• This will simply swap values and reduce a difficult case to an
easier one.
• If the node n to be deleted has no children,
• easy blow it away
• If it has one child
• Easy simply pass N’s child pointer up, make N’s parent point to N’s child
and blow N away
 Deletion by copying

• If n has two child,

Now we have deletion by copying.
• We find the smallest value in N’s right sub-tree
• We will take the value from that node and put it in place of the value in N.
• We will then blow away the node that had the smallest value in it.
• If n has two child,
Now we have deletion by copying.
• We find the smallest value in N’s right sub-tree
• We will take the value from that node and put it in place of the value in N.
• We will then blow away the node that had the smallest value in it.
Any questions..??