Binary Trees
A binary tree is a finite set of elements that is either empty
or is partitioned into three disjoint subsets. The first subset
contains a single element called the root of the tree.
The other two subsets are themselves binary trees, called
the left and right subtrees of the original tree. A left or
right subtree can be empty. Each element of a binary tree
is called a node of the tree.
Binary Tree
Example
A
B C
D E F
G H I
This tree consists of nine nodes with A as its root. Its left subtree
is rooted at B and its right subtree is rooted at C. The binary trees
rooted at D,G,H and I have empty right and left subtrees.
A node that has no children nodes is called a leaf node.
Node n1 is an ancestor of node n2 if n1 is either the father of n2
or the father of some ancestor of n2.For example A is the ancestor
of G, and H is a descendant of C but E is neither an ancestor nor
a descendant of C.
A node n2 is left descendant of node n1 if n2 is either the left son
of n1 or a descendant of the left son of n1.
Level of a node
A level of a node in a binary tree is defined as root of the
tree has level 0, and the level of any other node in the tree
is one more than the level of its father node.
For example in binary tree of Figure 1, node E is at level 2
and node H is at level 3.
Depth of binary tree
The depth of a binary tree is the maximum level of any
leaf in the tree. This equals the length of the longest path
from the root to any leaf. Thus the depth of the tree of
Figure 1 is 3.
Degenerated tree
If every non leaf node contains either left subtree or
right subtree.
Strictly binary tree
If every non leaf node in a binary tree has non empty
left and right subtrees the tree is termed as strictly
binary tree.
Strictly binary Tree??
Example
A
B C
D E F
G H I
Strictly binary Tree??
No. why?
A
B C
D E F
G H I
Strictly binary Tree??
B F
D E
Strictly binary Tree??
Yes
A
B F
D E
Strictly binary tree
If every non leaf node in a binary tree has non empty
left and right subtrees the tree is termed as strictly
binary tree.
A strictly binary tree with n leaves always contain
2n-1 nodes.
Complete binary tree
A complete binary tree of depth d is the strictly
binary tree all of whose leaves are at level d.
Complete binary tree??
Examples
A
B C
D E
Complete binary tree??
No.
A
B C
D E
Complete binary Tree
Example
A
B C
D E H F
Types of Binary Trees
Degenerate – only one child
Complete – always two children
Degenerat Complete
e binary binary
Almost complete binary tree
A binary tree of depth d is an almost complete binary
tree if
1. Any node nd at level less than d-1 has two children
nodes.
Almost complete binary tree
A binary tree of depth d is an almost complete binary
tree if
1. Any node nd at level less than d-1 has two children
nodes.
2. For any node nd in the tree with a right descendant
at level d, nd must have a left descendant at the
same level and every left descendant of nd is either
a leaf at level d or has two sons.
Example 1
Example 1 (No, 1st rule)
Example 2
Example 2 (No. Rule 2)
Example 3(Yes)
Example 4
BST
Binary search tree
Values in left subtree less than parent
Values in right subtree greater than parent
Facilitates duplicate elimination.
BST example
Traversal
Inorder
Preorder
postorder
Traversal
Inorder
Traverse left subtree
Visit root node
Traverse right subtree
Traversal
Preorder
Visit root node
Traverse left subtree
Traverse right subtree
Traversal
Postorder
Traverse left subtree
Traverse right subtree
Visit root node
Example 1
Find Inorder, preorder and post order traversal of
the following binary tree.
(a) Inorder (Left, Root, Right) : 4 2 5 1 3
(b) Preorder (Root, Left, Right) : 1 2 4 5 3
(c) Postorder (Left, Right, Root) : 4 5 2 3 1
Example 2
Inorder traversal
Post-order traversal
BST Operations
1)Find: Find node with key X
Start at root
Compare X against value in node
Branch left or right according to result of comparison
2) FindMin: Find smallest node in tree
Start at root
Follow left subtree until a null child pointer is found
3) FindMax: Find largest node in tree
Start at root
Follow right subtree until a null child pointer is found
4) Insert: Insert node with key X
Start at root or create new root node and stop
Branch left or right depending on key
Continue branching as required until you hit null
Create a new node with key X and assign to parent link
5) Delete: node with key X
Find node to remove
3 cases: target node has 0,1,2 children
0 children: just unlink from parent; 1 child: link child to Parent
2 children: use “replace with min” strategy
BINARY SEARCH TREE
typedef struct mytree
{ data
int data
struct mytree *left,*right; left right
}tree;
tree *root=NULL;
tree * create(tree *root, int data)
{ if (root==NULL)
{
root=(tree *)malloc(size of (tree));
root->left=root->right=NULL;
root->data=data;
}
else if(data<root->data)
{ root->left=create(root->left,data); }
else if(data>root->data)
{ root->right=create(root->right,data); }
else if(data==root->data)
{ printf(“Redundancy Error, Cannot Insert”); }
return root;
}
