Q1. In-place convert a Binary Search Trees into a sorted doubly linked list.
Q2. Find the sum of the nodes at a given level. Root is considered to be at level zero.
Q3. Find the sum of the nodes which are at a given distance d from any of their leaf nodes. Distance between two nodes is measured as the smallest number of edges that needs to be traversed to reach from one to the other.
Q4. Write a program to insert and delete a value from a Ternary Search Tree. A ternary search tree has 3 children. A ternary search tree belongs to the family of tries/prefix trees.
Q5. Merge two Binary Search Trees to create a new Binary Search Tree.
Q6. a) Given two nodes of tree, find the lowest common ancestor of the nodes.
Tarjan's lowest common ancestor algorithm
Least Common Ancestor Problem
b) Given two values and a binary search tree, find their lowest common ancestor.
Hint : Search for both the number simultaneously. The lowest common ancestor is the node where the search path bifurcates, i.e., the search path of one value goes to he left and other goes to the right.
Q7. Find the difference of the number of the left children to the number of right children for each node in a binary tree.
Q8. Given a Binary Tree, find the shortest path from root whose sum is S.
Q9. Design an algorithm to find if two trees are isotropic.
Q10. Design an algorithm to print the boundary of a binary tree. Boundary consists of the left most nodes, the leaf nodes, and the rightmost nodes. The order of output is top to bottom, left to right and finally bottom to top.
Example:
Q2. Find the sum of the nodes at a given level. Root is considered to be at level zero.
Q3. Find the sum of the nodes which are at a given distance d from any of their leaf nodes. Distance between two nodes is measured as the smallest number of edges that needs to be traversed to reach from one to the other.
Q4. Write a program to insert and delete a value from a Ternary Search Tree. A ternary search tree has 3 children. A ternary search tree belongs to the family of tries/prefix trees.
Q5. Merge two Binary Search Trees to create a new Binary Search Tree.
Q6. a) Given two nodes of tree, find the lowest common ancestor of the nodes.
Tarjan's lowest common ancestor algorithm
Least Common Ancestor Problem
b) Given two values and a binary search tree, find their lowest common ancestor.
Hint : Search for both the number simultaneously. The lowest common ancestor is the node where the search path bifurcates, i.e., the search path of one value goes to he left and other goes to the right.
Q7. Find the difference of the number of the left children to the number of right children for each node in a binary tree.
Q8. Given a Binary Tree, find the shortest path from root whose sum is S.
Q9. Design an algorithm to find if two trees are isotropic.
Q10. Design an algorithm to print the boundary of a binary tree. Boundary consists of the left most nodes, the leaf nodes, and the rightmost nodes. The order of output is top to bottom, left to right and finally bottom to top.
Example:
Boundary: 1 2 4 7 8 9 6 3
Hint: Preorder traversal till the leftmost node, print remaining leaves, reverse print preorder traversal till the rightmost leaf
No comments:
Post a Comment