Binary Search Tree

Questions On Binary Search Tree

All of the below solutions is in continuation of the Binary search Tree program which is written with this post therefore I am not passing root to every method, it is referred from the BinarySeachTree class.

Problem 1: Write a program to print the nodes by levels.
For example in below tree it should print – 6,4,9,2,5,7
BT-6

This is nothing but the Breadth First search. You will have to use a Queue to track the nodes.

Problem 2: Write a program to check whether a tree is Binary Search Tree or not.
You just traverse node by node and check for the Binary Search Tree conditions.

Problem 3: Write a program to Find lowest common ancestor of two nodes.
For example in below tree – the lowest common ancestor for 2 and 5 will be 4, the lowest common ancestor for 4 and 7 will 6.
BT-6

Problem 4: Write a program to compute the size of a Binary Search Tree.
We can easily define it recursively. It will be the sizeOf(left tree) + sizeOf(right tree) + 1 (root).

Problem 5: Write a program to find largest Binary Search Tree in a tree.

Problem 5: Write a program to create mirror image of a Binary Search Tree.

Problem 6: Write a program to check whether a BST is mirror image of other BST.

Problem 7: Write a program to find the height of a Binary Search Tree.

References
Design and Analysis of Algorithm – Anany Levitin
Beginning Algorithm – Simon Harris, James Ross
Data Structures And Algorithms In Java- Robert Lafore
Introduction_to_algorithms- Corman