Unit-4 Tree- Data Structures | BCA 3rd sem

Unit-4 Tree- Data Structures | BCA 3rd sem- Hello everyone welcome to the pencilchampions.com website. This website provide Data structures unit-4 Tree . Thankyou for visiting pencilchampions.com.

Introduction of Tree

• Tree is one of the most powerful and advanced data structure.
• Tree is a collection of elements called Nodes, where each node can have children.
• Tree is a hierarchical data structure which stores the information naturally in the form of hierarchy style.
• Tree is one of the most powerful and advanced data structures.
• It is a non-linear data structure compared to arrays, linked lists, stack and queue.
• It represents the nodes connected by edges.
• Tree is a collection of elements called Nodes, where each node can have arbitrary number of children.
• In the above figure, D, F, H, G are leaves. B and C are siblings. Each node excluding a root is connected by a direct edge from exactly one other node
  parent →  children.

Read external link-https://bcastudyguide.com/

Levels of a node

• Levels of a node represents the number of connections between the node and the root. It represents generation of a node.

There are three techniques of traversal:

1. Preorder Traversal
   2.Postorder Traversal
   3. Inorder Traversal

Binary Tree

• Binary tree is a special type of data structure.
• The above tree represents binary tree in which node A has two children B and C. Each children have one child namely D and E respectively.

Representation of Binary Tree using Array

• Array index is a value in tree nodes and array value gives to the parent node of that particular index or node. Value of the root node index is always -1 as there is no parent for root. 

Binary Search Tree

• Binary search tree is a binary tree which has special property called BST.

For all nodes A and B, 

1. If B belongs to the left subtree of A, the key at B is less than the key at A.
2. If B belongs to the right subtree of A, the key at B is greater than the key at A.

Each node has following attributes:

1. Parent (P), left, right which are pointers to the parent (P), left child and right child respectively.

Definition:

“Binary Search Tree is a binary tree where each node contains only smaller values in its left subtree and only larger values in its right subtree.”

• The above tree represents binary search tree (BST) where left subtree of every node contains smaller values and right subtree of every node contains larger value.
• It focuses on the search operation in binary tree.

Binary Search Tree Operations

1. Insert Operation

• Insert operation starts from the root node.

2. Search Operation

• This operation starts from the root node.

There are four types of binary tree:

1. Full Binary Tree
2. Complete Binary Tree
3. Skewed Binary Tree
4. Extended Binary Tree
   

   ---

   Read more-https://pencilchampions.com/unit-3-linked-list-data-structures-bca-3rd-semester-2023/

   ---