Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
You can use same normal BST verification with min and max but at each recursive call, need to check if root->data is not same as left or right data.
what if the duplicated value is not a child of the corresponding parent node?
will the above method still work?
if duplicates is allowed in BST, then insertion will be with:
i) add new key to left subtree if key is less than or equal to root key
or
ii) add new key to right subtree if key is greater than or equal to root key
Taking (i):
For tree
5
3
5
4
5 is root
3 is left to root(5)
next 5 is right to 3
4 is left to 5 (below)
in this tree, 3 is smaller than 5 so in left subtree to 5.
next 5 is less than or equal to root 5 so in left subtree of root (that is 5) and this new 5 is greater than 3 so in right subtree of 3.
So now, 5 is not immediate children of root (5).
We can find the inorder traversal of the tree and check if the data in every left node is less than (not less than or equal to) to the data in it's right node. If it is a BST then the duplicate elements will be consecutive in the inorder traversal.
This is a very simple slution. The inorder traversal can be done either using recursion or the iterative method.
It can be done as follows:
- Ricky February 03, 2014