DS - Unit-3 Previous Questions

Syllabus

Trees: Importance of Trees, Basic Tree Concepts and Terminologies: node, path, degree, internal nodes, height and subtree.

Binary Tree: Binary Trees, Binary Tree Representations, Representing Lists as Binary trees, Minimum nodes, Maximum nodes, Nearly complete binary tree – Tree Traversals Depth First Traversal (Preorder, Inorder and Postorder), Breadth First Traversal, Construction of Expression Tree.

Binary Search Tree: Binary Search Trees – Basic Concepts, Operations (Insertion, Deletion, Find the smallest node, Find the largest node, and Find a requested node), Applications, Threaded Binary Trees.

SEMESTER END EXAMINATIONS – JUNE 2024

Find the following in the tree given: i. Balance factor of the tree. ii. Show the depth first traversal (preorder, inorder and postorder) of the tree. iii. Show the breadth first traversal of the tree.

                           10
                        /      \
                      8         11
                    /              \
                  2                 14
                /   \              /    \
              1      6            13    16
                    / 
	               4   
                 / \
                3   5

Write algorithms to find Smallest node and largest node in a Binary Search Tree.

Define an Expression tree. Construct the Expression tree for the following: i. ( a / ( b + c )) + (((d / e) - f) * g) ii. (A+B*C)$ ((D+E)*F)

A+(B-C)*D$(E*F) (A+B*C)$ ((D+E)*F)

List the applications of Binary Search Tree. Create a binary search tree using the following data entered as a sequential set: 14,15,12,23,5,7,7,10,33,80,66 Also perform inorder and preorder traversal for the created tree.

With suitable example, illustrate Threaded Binary tree.

Explain the Level of a tree with example. In a Binary Tree what is the maximum number of nodes that can be found in level 12.

BACKLOG SUBJECT EXAMINATIONS – SEPTEMBER / OCTOBER 2023

With a suitable examples, define the following: i) Binary tree ii) Degree of a node iii) Level of a binary tree iv) Complete binary tree v) Almost complete binary tree.

Construct the Binary search for the following set of numbers 14, 17, 11, 7, 53, 4, 13, 12, 8, 60, 19, 16. Perform inorder, preorder and postorder traversals of the obtained tree.

Define expression tree. Write the procedure to construct the expression tree from an infix expression.

Explain threaded binary trees and their representation with a neat diagram. Also develop function to do the inorder traversal of a threaded binary tree.

Write C function to find the maximum element in BST.

SEMESTER END EXAMINATIONS – MAY / JUNE 2023

Traverse the given tree using Inorder and Postorder traversals.

                        A
                    /       \
                  B           C
               /    \       /    \
             D       E    F      G
               \               /   \
	            H             I     J

Write an algorithm to insert and delete an element in a Binary Search Tree.

What area threaded tree and its advantage?

Write the algorithm for Binary Tree Inorder, Preorder and Postorder traversal.

Define Binary Tree, Complete Tree and nearly complete Tree. Give one example for each.

Construct the Binary Search Tree (BST) from the following elements by considering each character as one element. D A T A S T R U C T U R E A N D A L G O R I T H M S

SUPPLEMENTARY SEMESTER EXAMINATIONS - NOVEMBER 2022

What is Binary Search Tree? Create a binary search tree using the following data entered as a sequential set: 14,15,12,23,5,7,7,10,33,80,66

Explain the following terms with suitable examples. i. Binary Tree ii. Nearly Complete Binary Tree iii. Complete Binary Tree iv. Height of a tree v. Binary Search Tree.

Find the following in the tree given:

                        125
                    /        \
                  15          50
                /   \       /     \
              10     22   35      70
            /  \   /  \  /  \    /    \
           4   12 18  24 31  44 66    90

i) Balance factor of the tree. ii) Show the depth first traversal (preorder, inorder and postorder) of the tree. iii. Show the breadth first traversal of the tree.

Construct the Expression tree for the following: i. (M / (N + O)) + (((P / Q) - R) * S) ii. (A+B*C)$ ((D+E)*F)

Generate Binary Tree looking into the following tree traversals: Preorder: ABDGCEHIF Inorder: DGBAHEICF

SEMESTER END EXAMINATIONS – JUNE 2022

Construct the Binary Search Tree (BST) from the following elements: D A T A S T R U C T U R E S U S I N G C also write the in-order, pre-order and post-order traversals for the BST generated.

Explain algorithm to delete a node from the Binary Search Tree (BST) with an appropriate example.

Give the algorithms for pre-order and post-order tree traversals. Represent the following expression using binary tree and write the pre-order and Post-order traversals for the tree generated. A+(B-C)*D$(E*F)

Define and give an example for Threaded Binary tree.

Define the following and give suitable example for each: i) Complete Binary tree ii) Nearly complete Binary tree iii) Binary search tree.

EXAMINATIONS SEPTEMBER /OCTOBER 2021

Construct the Binary Search Tree (BST) from the following elements D A T A S T R U C T U R E A N D A L G O R I T H M S also write the in-order, pre-order and post-order traversals for the BST generated.

Write short note on: Threaded Binary Tree.

Represent the following expressions using binary tree: i. A+(B-C)*D$(E*F) ii. (A+B*C)$ ((D+E)*F)

Generate binary trees looking into the following tree traversals. i. Inorder: E A C K F H D B G Preorder: F A E K C D H G B

ii. Inorder : 2 6 7 1 4 8 3 5 9 Postorder: 7 6 2 8 4 9 5 3 1

i. Preorder: ABDGCEHIF; Inorder: DGBAHEICF

ii. Postorder: IEJFCGKLHDBA; Inorder: EICFJBGDKHLA

Define Binary Tree, Complete Tree and nearly complete Tree. Give one example for each.

Write algorithms to perform the following operations on a BST: i. Search for a requested node ii. Add a new node.

SEMESTER END EXAMINATIONS – JULY / AUGUST 2021

Explain the following terms with suitable examples. i. Binary Tree ii. Complete Binary Tree iii. Expression Tree iv. Binary Search Tree.

Create a binary search tree using the following data entered as a sequential set: 14,15,12,23,5,7,7,10,33,80,66

Find the following in the tree given:

Tree of 2 branches and 11 nodes

Balance factor of the tree. Show the depth first traversal (preorder, inorder and postorder) of the tree. Show the breadth first traversal of the tree.

Construct the Expression tree for the following: i. ( a / ( b + c )) + (((d / e) - f) * g) ii. (5+6*7)$((5+6)*7))

Define Threaded Binary Tree and show its representation.

EXAMINATIONS SEPTEMBER /OCTOBER 2020

Give the properties of binary trees that distinguish them from general trees.

Explain how to change a general tree into a binary tree with an example.

Write an algorithm to delete a node from the Binary Search Tree (BST). Explain with an appropriate example.

Give the algorithms for preorder and postorder tree traversals. Represent the following expression using binary tree and write the preorder and postorder traversals for the tree generated. A+(B-C)*D$(E*F)

Write the algorithms for the following operations in Binary Search Tree (BST). i) Smallest node in a BST ii) Add node to BST iii) Search an item in a BST