Follow Me

Binary trees exercises in C Programming in C

  • Mystery function: What value does the following C function return?int mystery(Btree x){    if (x == NULL)        return 0;    else        return max(mystery(x->left), mystery(x->right));}...
  • Maximum value in a Binary tree of integers: Write each time a function that returns the maximum value of all the nodes in a binary tree of integers. Assume all values are nonnegative; return -1 if the tree is empty. recursive function iterartive using a queue iterative using a stack ...
  • Printing some values of a binary tree of integers: Write a recursive function that prints all the nodes less than a given value \(v\) in a binary tree of integers....
  • Sum of values in a binary tree of integers: Write a recursive function that returns the sum of all the nodes in a binary tree of integers....
  • Number of nodes in a binary tree of integers: Write a recursive function that counts the number of nodes in a binary tree of integers....
  • Level of a binary tree having the highest sum: Write a function that returns the level having the highest sum of its values. We assume that the root of the tree is at level 1, and that the tree is dynamically implemented. Without performing any calculations, give the worst case time complexity of...
  • Checking if a binary tree is a sumTree: A binary tree is called \(\texttt{SumTree}\) if the value of each non-leaf node is equal to the sum of the nodes present in its left subtree and its right subtree.An empty tree is considered as a \(\texttt{SumTree}\) and the sum of an empty tree is e...
  • Balanced binary trees: A binary tree is said to be balanced if both of its subtrees are balanced and the height of its left subtree differs from the height of its right subtree by at most 1. Write a C function to determine whether a given binary tree is balanced....
  • Depth and height of binary trees: Write a function that returns the depth/height of a binary tree. ...
  • Leaf nodes in binary trees: Write a function that counts the number of leaf nodes in a binary tree....
  • Non Leaf nodes in binary trees: Write a function that counts the number of non-leaf nodes in a binary tree....
  • Width of binary trees - iterative version: Write a function that computes the maximum width of a dynamically implemented BT. We define the maximum width of a BT as the maximum number of nodes located at the same level....
  • Comb left binary trees: A comb left is a locally complete binary tree (each node has 0 or 2 children) in which each right child of a node is a leaf. Write a function $\texttt{isLeftComb}$ that checks if a binary tree is a left comb. **img**isLeftComb.png##img##...
  • Trees Traversal: Consider the following tree: **img**bsttraversals01.png##img## Give the inorder traversal of the above tree. Write a recursive function that prints the inorder traversal of a tree dynamically implemented. Write an iterative function that prints the...
  • Statically implemented Binary Tree: Write a recursive function $\texttt{int max$\_$rec(Btree B, int root$\_$index)}$ that returns the maximum element in a binary tree statically implemented rooted at index $\texttt{root$\_$index}$.Example: Consider the following Binary tree and its r...
  • Zig zag level order: Write a function that takes as input a binary tree dynamically implemented and print out the tree in $$\texttt{zig zag}$$ level order (i.e., from left to right, then right to left for the next level and alternate between).  Example: **img**zigzag.p...
  • Maximum width and depth: We define the maximum width of a BT as the maximum number of nodes located at the same level, and the maximum depth as the longest path from the root to a leaf.  Write a function that computes the maximum width of a dynamically implemented BT. Wri...
  • Statically implemented Complete Binary Tree: A binary tree is called complete if all its non-leaf nodes have two children. Write a function that tests whether a binary tree statically implemented is complete....
  • Deepest element in a binary tree: Write a function $\texttt{deepest(A, E)}$ that returns the deepest level of the element E in the binary tree A or 0 if E $\notin$ A. We assume that the root of the tree is at level 1, and that the tree is dynamically implemented.  Running example: ...
  • Fairly well developed binary tree: We define the width of a level of a BT as the number of nodes located at this level. A BT is a fairly well developed if the width of each level of the BT is $>$ than the one of the previous level. Write a function that determines whether a BT is ...
  • 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(...
  • Boolean expression: A Boolean expression is represented as a binary tree of strings (BT) in which internal nodes contain the logical connectors $$\texttt{AND}$$, $$\texttt{OR}$$ and $$\texttt{NOT}$$, and leaves contain strings representing Boolean variables. Ex: the ex...
  • Binary trees insertion: Write a recursive function to insert an element, passed as a parameter, into a binary tree. If the root is empty, the new entry should be inserted into the root, otherwise it should be inserted into the shorter of the two subtrees of the root (or int...
  • Printing a Binary tree: Write a function that will print all the elements from a binary tree in the bracketed form (data: LT, RT) where data is the element in the root, LT denotes the left subtree of the root printed in bracketed form, and RT denotes the right subtree in br...
  • Binary tree mirrors: Write a function that will interchange all left and right subtrees in a binary tree. **img**interchangebt.png##img##...
  • Common entries in two binary trees: Write a function that returns the number of common entries in two BTs....
  • Searching for an element in a Binary tree: Write a function for searching an element in a binary tree....
  • Reverse level order: Write a function that prints the level order data in reverse order. For example, the output for the below tree should be: 0 9 11 8 15 7 35 5 **img**zigzag.png##img##...
  • Deepest node of the binary tree: Write a function to find the deepest node of the binary tree....
  • Half nodes in binary trees: Write a function that counts the number of half nodes (nodes with only one child) in the binary tree without using recursion....
  • Identical binary trees: Write a function that checks whether two binary trees are structurally identical....
  • Width of binary trees - recursive version: Write a function that computes the maximum width of a dynamically implemented BT. We define the maximum width of a BT as the maximum number of nodes located at the same level....
  • Binary tree mirrors check: Write a function that checks whether two binary trees are mirrors of each other **img**interchangebt1.png##img##...
  • Ancestors of a node in a Binary tree: Write a function that prints all the ancestors of a node in a Binary tree. For the tree below, and for 9 the ancestors are 9 2 6. **img**printbtree.png##img##...
  • Height of a generic tree: Given a parent array Parent, where Parent[i] indicates the parent of ith node in the tree (assume parent of root node is indicated with –1). Write a fucntion that finds the height or depth of the tree. Example:  If Parent is the following $ \begin...
  • Isomorphic binary trees: Write a function that checks whether tow binary trees are isomorphic. Two binary trees rare isomorphic if they have the same structure. The values of the nodes does not affect whether two trees are isomorphic or not. **img**isomorphic.png##img## **i...
  • Quasi-Isomorphic binary trees: Write a function that checks whether tow binary trees are quasi-isomorphic. Two binary trees rare isomorphic if they have the same structure. The values of the nodes does not affect whether two trees are isomorphic or not. Two binary trees B and C a...
  • Construction of k-ary tree: A full k –ary tree is a tree where each node has either 0 or k children. Given an array which contains the preorder traversal of full k–ary tree, write a function that construct the full k –ary tree. **img**narytree1.png##img##...
  • Ancestor sum in binary trees: A complete binary tree is a binary tree in which all level are completely filled: each non-leaf node has exactly 2 children and all leaves are located in the same level. Thus a tree of depth $n$ has 2$n$-1 nodes (1+2+4+8+$\cdots$). In this exercise, ...
  • Updating nodes in binary trees: Consider a binary tree of integers dynamically implemented; write a function update that changes node values such that each node is equal to the sum of its children. It is obvious that leaves remain unchanged.  Example: **img**updatetree.png##img## ...
  • Display elements at odd level in binary trees: Write a function that displays the elements of a binary tree located at odd left to right and top to bottom. The root of the tree is assumed to be at level 0. Example: **img**bsttraversals01.png##img## Expected result: 25 11 30 45...
  • Nearest common ancestors in binary trees: Write a function that returns the value of the father of a given element in a binary tree of integers without repetition. Write a function that returns an array containing the values of all ancestors of a given element in a binary tree of integers wi...
  • Leftist binary trees: Consider a binary tree T. We define the path from the root to a leaf as the number of edges from the root to that leaf. The minimum path in a tree $T$ is the shortest path among all paths between the root and all leaves. Write a function $\texttt{int...
  • Domain inclusion of heaps: A min-heap is a complete binary tree where the value of each element is less than the values of its children, if any.  Remark: each value is unique in a heap (it can't be repeated). Define the data structure for dynamic implementation of a heap of i...
  • Level with maximum sum in binary trees: Write a function that finds the level that has the maximum sum in the binary tree....
  • Path with a given sum in binary trees: Write a function that checks whether a path with given sum exists in the tree. ...
  • 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...

Back to the list of exercises