ASSIGNMENT # 2

DATA STRUCTURE

Name : Muhammad Saad

ID : 221310
Submitted to : Sir Junaid Mustafa
Q : What is the Tree data structure, explain briefly all terms related to tree data structure?
Ans :A tree is a hierarchical data structure that consists of nodes connected by edges. Each node
in a tree has a parent-child relationship with other nodes. The topmost node in a tree is called the
"root," and the nodes with no children are called "leaves." The edges represent the relationships
between nodes.
Here are some key terms related to tree data structures:
1. Node: A fundamental unit of a tree that contains data and may have a reference to one or more
child nodes.
2. Root: The topmost node in a tree, from which all other nodes are descended. A tree has only
one root.
3. Parent: A node in a tree that has one or more child nodes. The node immediately above a
given node is its parent.
4. Child: A node in a tree that has a parent node. Nodes with the same parent are called siblings.
5. Leaf: A node in a tree that has no children, i.e., it is at the bottom level of the tree.
6. Subtree: A tree formed by a node and all its descendants (children, grandchildren, etc.).
7. Depth: The level or distance of a node from the root. The root has a depth of 0, its children
have a depth of 1, and so on.
8. Height (or Depth): The length of the longest path from a node to a leaf. The height of the root
is the height of the entire tree.
9. Binary Tree: A tree in which each node has at most two children: a left child and a right
child.
10. Binary Search Tree (BST): A binary tree with the property that for each node, all nodes in
its left subtree have values less than the node's value, and all nodes in its right subtree have
values greater than the node's value.
11. Traversal: The process of visiting all the nodes in a tree. Common traversal methods include
in-order, pre-order, and post-order traversals.
- In-order traversal: Visit the left subtree, then the root, and finally the right subtree.
- Pre-order traversal: Visit the root, then the left subtree, and finally the right subtree.
- Post-order traversal: Visit the left subtree, then the right subtree, and finally the root.
12. Forest: A collection of disjoint trees.
Q : What is Binary search tree ?
Ans : A Binary Search Tree (BST) is a binary tree data structure with the following properties:
1. Binary Tree Structure: Each node in a BST has at most two children—a left child and a right
child.
[Link] Property: For each node in the tree, all nodes in its left subtree have values less than
the node's value, and all nodes in its right subtree have values greater than the node's value.
This ordering property makes searching for a specific value in the tree more efficient, as it allows
for a binary search algorithm. Because of this property, the BST supports quick insertion,
deletion, and retrieval operations.
Here's a visual representation of a simple BST:
5
/\
3 8
/| |\
14 79
In this example:
- The root is 5.
- The left subtree of the root (nodes 3, 1, and 4) contains values less than 5.
- The right subtree of the root (nodes 8, 7, and 9) contains values greater than 5.
For any given node, the values in its left and right subtrees follow the same ordering property,
making it easy to perform binary search operations. The time complexity of searching, insertion,
and deletion in a balanced BST is O(log n) on average, where n is the number of nodes in the
tree.
It's important to note that the efficiency of a BST depends on its balance. A well-balanced BST
ensures that the height of the tree remains logarithmic, leading to optimal performance. If a BST
becomes unbalanced (e.g., due to insertion of already sorted data), its performance can degrade
to O(n) in the worst case, where n is the number of nodes. To address this, self-balancing binary
search trees (e.g., AVL trees, Red-Black trees) are used to automatically maintain balance during
operations.
Q : How to traverse the binary search tree ?
Ans : Traversing a binary search tree (BST) means visiting all the nodes in a specific order.
There are three common methods for traversing a binary search tree:
1. In-Order Traversal:
- Visit the left subtree.
- Visit the root.
- Visit the right subtree.
In the context of a BST, in-order traversal visits the nodes in ascending order, as it first explores
the left subtree (containing smaller values), then visits the current node, and finally explores the
right subtree (containing larger values).
Example:
4
/\
2 6
/\/\
1 35 7
In-order traversal: 1, 2, 3, 4, 5, 6, 7
2. Pre-Order Traversal:
- Visit the root.
- Visit the left subtree.
- Visit the right subtree.
Pre-order traversal explores the current node before its subtrees. In the context of a BST, it can
be used to create a copy of the tree.
Example:
4
/\
2 6
/\/\
1 35 7
 Pre-order traversal: 4, 2, 1, 3, 6, 5, 7
3. Post-Order Traversal:
- Visit the left subtree.
- Visit the right subtree.
- Visit the root.
Post-order traversal explores the subtrees before the current node. In the context of a BST, it can
be used to delete all nodes, starting from the leaves and moving towards the root.
Example:
4
/\
2 6
/\/\
1 35 7

Post-order traversal: 1, 3, 2, 5, 7, 6, 4
These traversal methods are recursive in nature and can be implemented using recursion or with
the help of an explicit stack to simulate the recursive behavior. Each traversal method provides a
different way to explore and process the nodes of a binary search tree based on the order in
which nodes are visited.