Binary Tree

BINARY TREE AND SPANNING OF TREE

Department of Information Technology Institute of Computing Bahauddin Zakariya University Multan Pakistan

Prepared by Mr. Ali Asad Sahu  Mr. Shuja Ahmad  Mr. Haroon Tariq  Mr. Shoaib Shera  Mr. Samiullah  Mr. Amjad Rahim  Mr. Jamshed Ahmad 

Motivation   

What ? Why ? How ?

Tree (Data structure) 



Used to represent hierarchal relationship between data elements. Tree as a data structure is used to organize our data in an specific order and has great importance in computer science.

Simple Tree





Tree  Nodes  Each node can have 0 or more children  A node can have at most one parent Binary tree  Tree with 0–2 children per node

Tree

Binary Tree



Terminology Root ⇒ no parent  Leaf ⇒ no child  Interior ⇒ non-leaf  Height ⇒ distance from root to leaf  Siblings ⇒ Nodes with same parents 

Root node Interior nodes Leaf nodes

Height

Binary Tree A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left sub-tree and the right subtree of the root.  A node cannot have more than two sub-trees but less than two.  If a new node is greater than its parent it goes to right side and if less to left side. 

A Binary Tree Model

Memory Model of Binary Tree 

In the implementation of binary trees the child’s of a node are pointed by two pointers and data is stored in the object itself.

Binary Search Trees 

Key property  Value

at node

 Smaller

values in left subtree  Larger values in right subtree  Example X

>Y X < Z

X

Y

Z



Examples 5 10 5

2

10

45

30

5

45

30 2

25

45

2

10

25

30

25 Binary search trees

Not a binary search tree

Importance of Trees   

 



Representing Algebraic formulas Searching large and dynamic lists Supports Very effective searching technique using binary search. Implemented using linked lists. Trees are used to organize databases and file systems. Unix or DOS/Windows file system

Spanning of Trees 



The process of inserting new data elements in tree data structure is called spanning of tree. How to build & maintain binary trees? Insertion  Deletion 



Maintain key property (invariant)  Smaller

values in left subtree  Larger values in right subtree

Binary Search Tree – Insertion 

Algorithm 1. 2. 3.

4.

Perform search for value X Search will end at node Y (if X not in tree) If X < Y, insert new leaf X as new left subtree for Y If X > Y, insert new leaf X as new right subtree for Y

Example Insertion 

Insert ( 20 ) 10 < 20, right

10 5 2

30 25

20

30 > 20, left 25 > 20, left 45

Insert 20 on left

28,8,4,36,85,9,23,41,30 2 8

3 6 8 4 4 1

2 3 9 8 5 3 0

Binary Search Tree – Deletion 

Algorithm 1. 2. 3.

Perform search for value X If X is a leaf, delete X Else a) Replace with largest value Y on left subtree OR smallest value Z on right subtree b) Delete replacement value (Y or Z) from subtree

Example Deletion (Leaf) 

Delete ( 25 ) 10 5

2

10 < 25, right 30

25

10 5

30 > 25, left 45

25 = 25, delete

2

30 45

Example Deletion (Internal Node) 

Delete ( 10 ) Delete ( 5 ) Delete ( 5 ) 10 5

2

5 30

25

Replacing 10 with largest value in left subtree

5 45

2

5 30

25 Replacing 5 with largest value in left subtree

2 45

2

30 25

45

Deleting leaf

Binary Tree Traversal How to reach our required node.  Standard Traversal Orders 1. Preorder NLR 2. Inorder LNR 3. Postorder LRN  Very Easy by using recursion. We have to follow three steps recursively for each node. 

PreOrder Traversal The algorithm of PreOrder traversal is following:  Recursive Definition 1. Process the root R 2. Traverse the left subtree of R in Preorder 3. Traverse the right subtree of R in Preorder 

PreOrder Traversal A

A

B C

B

E D

F

C

E D

Walking order A

B

C

D

E

Processing order

F

F

InOrder Traversal 



The algorithm of InOrder traversal is following: Recursive Definition

Traverse the left subtree of R in Inorder 2. Process the root R 3. Traverse the right subtree of R in Inorder 1.

InOrder Traversal A

A

B C

B

E D

F

C

E D

Walking order C

B D

A

Processing order

E F

F

PostOrder Traversal  

The algorithm of PostOrder traversal is following: Recursive Definition

Traverse the left subtree of R in Postorder 2. Traverse the right subtree of R in Postorder 3. Process the root R 1.

PostOrder Traversal A

A

B C

B

E D

F

C

E D

Walking order C

D

B

F

Processing order

E

A

F

Example

Whatever the mind can conceive and believe, the mind can achieve.