20XT37- Advanced Data Structures Lab – Problem Sheet 2
Target Date :18/07/24
1. Write a program to create a binary search tree such that, the first element is the root. The tree
cannot contain duplicate values. Perform the following operations on the created tree:
(a) Finding an element
(b) Finding the maximum element
(c) Left child of the given node
(d) Right child of the given node
(e) Traverse the tree in in-order, pre-order and post-order.
2. Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print all
the keys of tree in range k1 to k2. i.e. print all x such that k1.
3. You are given the root of a binary search tree (BST) and an integer val.
Find the node in the BST that the node's value equals val and return the subtree rooted with
that node. (display all the nodes in the subtree). If such a node does not exist, return null.
4. Given the root node of a binary search tree and two integers low and high, return the sum of
values of all nodes with a value in the inclusive range [low, high].
5. Write a recursive function BSTsmallcount that, given a BST and a value key, returns the
number of nodes having values less than key. Your function should visit as few nodes in the
BST as possible.
6. Given the root node of a binary search tree (BST) and a target value. The task is to find the k
values in the BST that are closest to the target value. The answer can be returned in any order.
It is guaranteed that there is only one unique set of k values in the BST that are closest to the
target.
Example:
Input: root = [5,3,6,2,4], target = 3.714286, k = 2
Output: [4,3]
7. In Ancient Greece, it was common to write text with the first line going left to
right, the second line going right to left, and continuing to go back and forth. This
style was called "boustrophedon". Given a binary search tree, write an algorithm
to print the nodes in boustrophedon order.
Example
10
5 20
3 7 17 25
Output : 10 20 5 3 7 17 25
