Jan 312017

Given an array of integers that represent values of nodes in a Binary Search Tree. For example, If the given array is

{9, 4, 17, 6, 5, 3, 7, 22, 20}

Then BST created from above array will be as below

Two numbers are given (along with the array), find largest number in the path between these two numbers in the BST.

For example, if above array is given and the two numbers are 4 and 20, the max number in the path from 4 to 20 is 22. Continue reading »

Aug 232012

Given a Binary Tree, write code to convert it to Binary Search Tree such that the structure of the tree remains the same. For example: Both the below trees

          5                        10
        /   \                    /    \
       8    10                  5     30
     /  \     \               /   \     \
    4   30     1             8    40     1
   /                        /
  40                       4

Should generate the below Binary Search Tree.

Note that the structure of the tree remains the same. Hence all the three trees above are Similar.
Continue reading »

Aug 182012

Given the PreOrder traversal of a binary search tree (in the form of a tree), check if all the nodes (except the last) of the tree has exactly one child.

For Example: If the Preorder traversal of the tree is given as below:

{50, 25, 45, 30, 27, 29}

The the output should be: TRUE

Because Binary Search Tree represented by the above traversal is shown on the right.

Continue reading »

Jul 302012

Earlier, we have seen how to find the minimum element in a Binary Search Tree.

Write a function which will return the maximum value in a binary search tree. For example: For the below Binary search tree, the function should return 40

Structure of the Node of the Tree is as given below:

    struct Node
        int data;
        Node* lptr; // Ptr to LEFT subtree
        Node* rptr; // ptr to RIGHT subtree

Continue reading »