Antoun J. Yaacoub Ph.D.

Binary search trees exercises in C Programming in C

Checking whether an element is in a Binary search tree: Write an iterative function that tests whether an element belongs to a $BST$....
Checking whether an element is in a Binary search tree using recursion: Write a recursive function that tests whether an element belongs to a $BST$....
Checking whether a given binary tree is a BST: Part 1 Write a function that checks whether a given binary tree is a BST or not. Consider the following simple program. For each node, check if the left node of it is smaller than the node and the right node is greater than the node. This approach is...
Checking whether elements of 2 BSTs are the same using an iterative function: Knowing that the inorder traversal of BSTs produces sorted lists, write an iterative function function that given 2 BSTs, the function checks whether the elements of both BSTs are the same or not. The time complexity of your algorithm should be $O(max(m, n))$...
Write a recursive function that checks whether an element belongs to a BST: Write a recursive function that checks whether an element belongs to a BST....
Write an iterative function that checks whether an element belongs to a BST: Write a iterative function that checks whether an element belongs to a BST....
Checking whether elements of 2 BSTs are the same using recursion: Given 2 BSTs, write a recursive function that checks whether the elements of both BSTs are the same or not. The time complexity of your algorithm should be $O(m\times n)$, where $m$ and $n$ are the numbers of elements in the two BSTs ....
Finding floor and ceil of a value in a Binary Search tree: Given a $\texttt{BST}$ containing $n$ nodes, write a function that runs in $\mathcal{O}(\log{}n)$ that finds the $\texttt{floor}$ and the $\texttt{ceil}$ of a value $\texttt{val}$ given as parameter.If $\texttt{val}$ exists in the tree, i...
Set of integer in binary search trees: We want to construct a binary search tree to represent a set of integer numbers. Unlike the traditional binary search tree where each node contains only one integer value, we want to allow each node to contain all the values between two bounds $$\tex...
Same elements in binary search trees: Give the declaration of a Binary Search Tree of integers ($$\texttt{BST}$$). Write a recursive function that checks whether an element belongs to a $$\texttt{BST}$$. Write an iterative function that checks whether an element belongs to a $$\texttt{...
Binary search trees in levels: We would like in this question to arrange words of any length in a tree structure represented in levels as follows: each node $$p$$ of the tree of level $$i$$ has the following structure: typedef char element;typedef struct node{ element ...
Checking whether a tree is a BST by traversing it in inorder: The following function checks whether a given binary tree dynamically implemented is a BST or not. int isBST(Btree tree){ if(tree == NULL) return 1; if(tree->left != NULL && FindMax(tree->left) > tree->data) retur...
Target sum in a BST: Given a Balanced Binary Search Tree and a target sum, write an iterative function that returns $$\texttt{true}$$ if there is a pair with sum equals to target sum, otherwise return $$\texttt{false}$$. Expected time complexity is $$\texttt{O(n)}$$. A...
Forest of Binary Search Trees: Consider a forest represented in the form of a linked list where each node points to a Binary Search Tree of words of length $$\texttt{L}$$. The list is sorted according to the length of the word. Example: After the insertion of the following words i...
Binary Search Tree of Events: A historian wants to classify a set of events. Each event is characterized by a $$\textit{title}$$, a $$\textit{location}$$ and a $$\textit{period}$$ of time (as most of the events are spread over several years). $$\textit{Title}$$ and $$\textit{loca...
Binary tree rotations: In a binary tree (BT), a path between the root and a leaf is the number of arcs joining the root to the leaf. The BT $$\texttt{height}$$ is the length of the longest path between the root and each of the leaves. Write a function $$\texttt{int height(...
Modified BST: Consider the following declaration of a BST in which the field nbd denotes the number of descendants of a tree node: typedef struct node{ element data ; int nbd ; struct node *Left, *Right ;} *BST; Write a function that inserts...
Common entries in two binary search trees: Write a function that returns the number of common entries in two BSTs....
Merging two binary search trees: Write a function that merges 2 BST into a new BST....
Distinct values in a binary search tree: We consider a variant of BST where $\texttt{left(n)}$ $\leq$ $n$ $<$ $\texttt{right(n)}$ and this for any node $\texttt{n}$ in the tree. Write a function that calculates the number of distinct values in this kind of binary tree. Give the corre...
Delete common elements in two binary search trees: Given 2 BST $\texttt{A}$ and $\texttt{B}$, write a function that deletes from $\texttt{B}$ all the common elements with $\texttt{A}$....
Static Binary Search Trees: A Binary Search Tree (BST) of whole integers can be represented by an array where the root is located at 0 and the contents of the remaining nodes correspond to the course in width of the tree. i.e. every node has two locations for its left and right...
Binary Search Trees Variant: We consider a variant of binary search trees in which $left(n) ≤ n < right(n)$ and this for any node $n$ of the tree. Given two binary search trees $A$ and $B$, we are interested in removing from the tree $B$ all the elements that are common to ...
Hashing with BSTs: Consider a hash table with chaining where the elements with the same hash value are inserted in the same binary search tree (BST) instead of a list. Define the abstract data type (ADT) Hash Table. Write the corresponding declaration of such data stru...
Almost uniform hashing function: Consider a hash table with chaining where the elements (string) of same hash value are inserted in a binary search tree (BST) implemented dynamically. Give necessary declarations and write a function that returns an array that contains the number of ...
Hash coalesced with separated zones to separate chaining with BSTs: We consider a hash table T$$_1$$[$$m$$] in which collisions are resolved by applying the hash coalesced with 2 separated zones: primary zone of size $$p$$ and a reserve zone of size $$r$$ ($$m=p+r$$). After adding many elements to T$$_1$$, there has ...
Different traversals output of a binary tree: Given the below binary tree, answer the following questions: **img**traversalbtexs12020.png##img## Give the output of the $$\texttt{inorder}$$, $$\texttt{preorder}$$, $$\texttt{postorder}$$ and $$\texttt{level order}$$ traversals of the above tree? I...
Stern-Brocot tree: The Stern-Brocot tree is an elegant construction to represent the set of all positive fractions. It was independently discovered by German mathematician Moritz Stern in 1858 and by French watchmaker Achille Brocot in 1861. The construction starts at ...

Back to the list of exercises

Select your ad blocker:

Disable AdBlock:

Disable AdBlock Plus:

Disable Adguard AdBlocker:

Disable uBlock Origin:

Binary search trees exercises in C Programming in C