dsa prsentation binary tree and its variants.

Binary trees in the dsa subject.

1. Topic : General and Binary
Trees

2. Group Members
•MinahilNadeem
•SaadSaaed
•LaibaRustum
•MubbashirMalik
2

3. General Tree :
❖A general tree is a hierarchical structure where each node can have any
number of children (zero or more).
❖In a general tree, each node has in-degree(number of parent nodes) one
and maximum out-degree(number of child nodes) n.
3

4. General Tree :
Monday, February 1, 20XX Sample Footer Text
4

5. General Tree :
Monday, February 1, 20XX Sample Footer Text
5
Real-life example:
Consider an organizational
chart of a company. Each
employee can have several
reporting managers or
subordinates, creating a
complex hierarchy.

6. .
Monday, February 1, 20XX Sample Footer Text
6

7. Binary Tree:
❖A binary tree is the specialized version of the General tree. A binary tree is a
tree in which each node can have at most two nodes.
❖The topmost node of a binary tree is called root node and there are mainly
two subtrees one isleft-subtreeand another isright-subtree.
7

8. Binary Tree :
8

9. Binary Tree :
Real-life example:
Imagine a family tree. Each
person can have two parents,
forming a binary branching
structure.
9

10. 10

11. Difference b/w General And Binary Tree :
11
Feature General Tree Binary Tree
Number of children per node Any number At most two (left and right)
Structure Complex, varying degree of branchingSimpler, consistent branching
Operations Standard traversal algorithms
Standard traversal algorithms + specific
binary tree traversals
Representations Node-based, parent-based Node-based, parent-based, array-based
Applications
Hierarchical relationships, file systems,
complex data
Data organization, retrieval, sorting,
searching
Special case None Binary search tree

12. Difference b/w General And Binary Tree :
Monday, February 1, 20XX
12

13. Representation of Binary Tree :
13
Array Representation :
In array representation of a binary tree, we use one-dimensional array (1-D Array) to
represent a binary tree.

14. Representation of Binary Tree :
Monday, February 1, 20XX Sample Footer Text
14
To represent a binary tree of depth'n'using array representation, we need one
dimensional array with a maximum size of2n + 1.

15. Representation of Binary Tree :
15
Linked List Representation of Binary Tree :
We use a double linked list to represent a binary tree. In a double linked list,
every node consists of three fields. First field for storing left child address,
second for storing actual data and third for storing right child address.

16. Representation of Binary Tree :
16

17. Traversal Techniques :
17
❖ForInorder,
you traverse from theleftsubtree to therootthen to therightsubtree.
❖ForPreorder,
you traverse from therootto theleftsubtree then to therightsubtree.
❖ForPost order,
you traverse from theleftsubtree to therightsubtree then to theroot.

18. 18

19. Binary Search Tree :
19
•It is called a binary tree because each tree node has a maximum of two
children.
•It is called a search tree because it can be used to search for the presence of
a number inO(log(n))time.

20. Binary Search Tree :
Real-life example:
Imagine a dictionary. Each word has a
specific alphabetical order, creating a
binary search tree where searching for
a word involves comparisons with
neighboring words.
Monday, February 1, 20XX Sample Footer Text
20

21. Monday, February 1, 20XX Sample Footer Text
21

22. Binary Search Tree :
Algorithm:
If node == NULL
return createNode(data)
if (data < node->data)
node->left = insert(node->left, data);
else if (data > node->data)
node->right = insert(node->right, data);
return node;
Monday, February 1, 20XX Sample Footer Text
22

23. Binary Search Tree :
Monday, February 1, 20XX Sample Footer Text
234<8 so, transverse through the left child of 8

24. Binary Search Tree :
Monday, February 1, 20XX Sample Footer Text
244>3 so, transverse through the right child of 8

25. Binary Search Tree :
Monday, February 1, 20XX Sample Footer Text
254<6 so, transverse through the left child of 6

26. Binary Search Tree :
Monday, February 1, 20XX Sample Footer Text
26Insert 4 as a left child of 6.

27. Monday, February 1, 20XX Sample Footer Text
27

28. •General tree
•Binary tree
•Representations
•Tree traversal
•Binary search tree
Monday, February 1, 20XX Sample Footer Text
28

29. Monday, February 1, 20XX Sample Footer Text
29