Amazon Interview Question Software Engineer / Developers
Do inorder traversal:
int outNum = 0;
findSmaller (root,&outNum,givenNum)
void findSmaller (node* root, int* outNum, int givenNum)
{
if (root)
{
findSmaller (root->left, outNum, givenNum);
if (root->data < givenNum)
{
*outNum = root->data;
}
findSmaller (root->right, outNum, givenNum);
}
}
why do you want to traverse both left and right.. the question says it is a binary search tree? Isn't the following sufficient,
1) first find the node which is equal to the given number.
2) If the node has left tree then traverse the last right node of left tree. That is the smallest near value to the given number
3) Else (no left tree).. If the found node is a right child (with respect to its parent) then the parent will be the smallest element.. If the found node is a left child (with respect to its parent) then we don't have any small value near to the given value
def findNextSmallest(head):
# If we don't have a left child and we are right node
# return the parent
if (head.left == None and head.parent != None and head.parent.right == head):
return head.parent
# If don't have a left child and we are the left node, go up the tree till
# we find a node smaller than the said value
if (head.left == None and head.parent != None and head.parent.left == head):
currNode = head
currVal = head.value
while(currNode != None and currVal <= currNode.value):
currNode = currNode.parent
return currNode
# follow the left node and continue down the right child subtree
returnNode = head.left
tRight = None
if (head.left != None and head.left.right != None):
tRight = head.left.right
while(tRight != None):
if (tRight.right == None):
returnNode = tRight
tRight = tRight.right
return returnNode
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
struct node
{
int data;
node *left,*right;
node()
{
}
node(int dat)
{
data=dat;
left=right=NULL;
}
};
class tree
{
node *root;
public:
tree()
{
root=NULL;
}
void add(int a)
{
node *p=new node(a);
if(root==NULL)
{
root=p;
return;
}
else
{
node *q=root,*r=NULL;
while(q!=NULL)
{
r=q;
if(a>q->data)
q=q->right;
else if(a<q->data)
q=q->left;
}
if(a<r->data)
r->left=p;
else
r->right=p;
}
}
void show(node *q)
{
if(q==NULL)
return ;
show(q->left);
cout<<q->data<<"\t";
show(q->right);
}
void show_in()
{
show(root);
}
int maximum(int max,int n,node *q)
{
if(q==NULL)
return max;
if(q->data<n)
{
max=q->data;
int temp=maximum(max,n,q->right);
return temp;
}
else
{
int temp=maximum(max,n,q->left);
return temp;
}
}
int max_n(int n)
{
int temp=maximum(-99999,n,root);
}
};
main()
{
tree t;
t.add(2);
t.add(5);
t.add(4);
t.add(81);
t.add(18);
t.add(20);
t.show_in();
cout<<"\n";
cout<<t.max_n(2)<<"\t";
cout<<t.max_n(5)<<"\t";
cout<<t.max_n(4)<<"\t";
cout<<t.max_n(81)<<"\t";
cout<<t.max_n(18)<<"\t";
cout<<t.max_n(20)<<"\t";
cout<<"\n";
}
int getMaxOneBeforeMaxVal(struct node *tree , int number) {
while(tree->right->right != NULL){
tree = tree->right;
}
return tree->num;
}
Isn't this the in-order predecessor?
The right-most node in the left sub tree
read the algorithm book first, guys
I found some more good information here: <a href="http://www.availhosting.com">reseller hosting</a>
Isn't it sufficient that we do this -
1. Perform normal binary search for N in the BST.
2. Every time we go down a right link of a node, remember the value of that node as 'best known maximum value smaller than N'.
3. While going down a right or a left link, it may be NULL. The two cases -
3a. If trying to go down the left link and link was found to be null, the current 'best known maximum value smaller than N' is the answer(in other words, the last node whose right link we took).
3b. If trying to go down the right link of a node and the link was found to be null then the node's value itself is the answer.
Rohit,
Isnt it "the value of the node where we took the last right turn" while searching for N, irrespective of we eventually find N or hit a NULL
Rohit,
Isnt it "the value of the node where we took the last right turn" while searching for N, irrespective of we eventually find N or hit a NULL
<pre lang="" line="1" title="CodeMonkey69888" class="run-this">/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package javaapplication1.BTreepack;
import java.util.Stack;
/**
*
* @author Lalit
*/
public class BTree {
Node root = null;
public boolean search(int data) {
Node n = new Node(data);
Node node = root;
while (node != null) {
if (node.equals(n)) {
return true;
}
if (node.left != null) {
if (n.data < node.data) {
node = node.left;
}
} else if (node.right != null) {
if (n.data > node.data) {
node = node.right;
}
} else {
return false;
}
}
return false;
}
public BTree(int data) {
root = new Node(data);
}
Stack st = new Stack(); // used to compute the largest number smaller than the number inputted
public void printLarge(int num){
Node current = root;
Node previous= current;
while(current!=null)
{
if(current.right== null && current.left== null )break;
//System.out.println("current.data"+current.data);
if(num<current.data){ // traverse left
if(current.left!=null){
previous=current;
st.push(current.data);
current= current.left;
// System.out.println("in 1st if"+current.data);
}
}
else if(num>=current.data){
if(current.right!=null){
previous=current;
st.push(current.data);
current= current.right;
// System.out.println("in 2nd if"+current.data);
}
}
}
while(!st.empty()){
//if((Integer)st.peek()<num)
if((Integer)st.peek()<num){System.out.println(st.peek());
st.pop();
return;}
st.pop();
// else
}
// System.out.println(previous.data);
//System.out.println(current.data);
}
public void insertNode(Node node, int value) {
if (node != null) {
// System.out.println(node.data);
if (value < node.data) {
if (node.left != null) {
insertNode(node.left, value);
} else {
Node insertedNode = new Node(value);
node.left = insertedNode;
// System.out.println(insertedNode.data);
}
} else {
if (value > node.data) {
if (node.right != null) {
insertNode(node.right, value);
} else {
Node insertedNode = new Node(value);
node.right = insertedNode;
// System.out.println(insertedNode.data);
}
}
}
}
}
public static void main(String args[]) {
BTree b = new BTree(10);
b.insertNode(b.root,5);
b.insertNode(b.root,3);
b.insertNode(b.root,8);
b.insertNode(b.root,1);
b.insertNode(b.root,4);
b.insertNode(b.root,7);
b.insertNode(b.root,9);
b.insertNode(b.root,11);
b.insertNode(b.root,13);
b.insertNode(b.root,17);
b.insertNode(b.root,21);
b.insertNode(b.root,15);
// b.printLarge(21);
b.printLarge(16);
// b.printLarge(9);
// b.printLarge(8);
//System.out.println(b.search(20));
//b.printNodes(b.root);
}
}
class Node {
int data;
Node right;
Node left;
public Node(int data) {
right = null;
left = null;
this.data = data;
}
public boolean equals(Node n) {
if (this.data == n.data) {
return true;
} else {
return false;
}
}
}
</pre><pre title="CodeMonkey69888" input="yes">
</pre>
public class BSTLargest {
public static class Node {
private int data;
private Node left;
private Node right;
public Node() {
super();
}
public Node(int data) {
super();
this.data = data;
}
}
private Node root;
public void insert(int data) {
if (root == null) {
root = new Node(data);
} else
insert(root, data);
}
private void insert(Node node, int data) {
if (node.data >= data) {
if (node.left == null) {
node.left = new Node(data);
} else {
insert(node.left, data);
}
} else if (node.data < data) {
if (node.right == null) {
node.right = new Node(data);
} else {
insert(node.right, data);
}
}
return;
}
public void printLarge(int data) {
printLarge0(root, data);
System.out.println(inoderSucc);
}
int inoderSucc = Integer.MIN_VALUE;
boolean found = false;
public void printLarge0(Node node, int data) {
if (node == null || found) {
return;
}
printLarge0(node.left, data);
if (node.data > data) {
found = true;
// System.out.println(inoderSucc);
} else {
inoderSucc = node.data;
}
printLarge0(node.right, data);
}
/**
* @param args
*/
public static void main(String[] args) {
BSTLargest bst = new BSTLargest();
bst.insert(5);
bst.insert(-1);
bst.insert(34);
bst.insert(12);
bst.insert(32);
bst.insert(102);
bst.insert(21);
bst.printLarge(20);
}
}
/// pass the root node of the BST, with the target value and lastval is the output
public void findLargestLeft(Node root,int target,int lastval){
if(root == null )
System.out.println( lastval);
else{
if(target<(Integer)root.getData())
{
// no need to update lastval
if(root.left == null)
System.out.println( lastval);
else
findLargestLeft(root.left,target,lastval);
}
if(target>(Integer)root.getData())
{
lastval = (Integer) root.getData();
if(root.right == null)
System.out.println( lastval);
else
findLargestLeft(root.right,target,lastval);
}
// if the value exist in the tree
if(target==(Integer)root.getData())
{
System.out.println( lastval);
}
}
}
// its basically asking for finding floor(n) in tree here is the code in java
public Node floor(Node x, Key key ){
if (x==null) return null;
if(cmp==0) return x;
int cmp = key.comparesTo(x.key) // assumed key as generic type that implements comparable
if(cmp<0)
return floor(x.left,key);
if(cmp>0){
Node t= floor(x.right,key);
if(t!=null) return t;// if right not null ....that would be preferred candidate
else
return x; // if right null.....return parent of this right;
}
}
/*
Here root : is the member variable of BST
K : it is the given value
path[] : it is an array of size 1
*/
public void findLargestSmallerNumberFromK(Node root,int k,int path[])
{
if(root == null)
return;
if(root.getData()<k)
{
path[0] = root.getData();
findLargestSmallerNumberFromK(root.getRight(),k,path);
}
else
{
findLargetSmallerNumberFromK(root.getLeft(),k,path)
}
}
public void findLargestSmallerNumberFromKWrapper(Node root,int k)
{
int path[] = new int[1];
findLargetSmallerNumberFromK(root,k,path);
System.out.println("Largest number in binary Tree which is smaller than K is" + path[0]);
}
{int BST::findLargestNumberSmallerThan(Node * node, int n) {
if (node == NULL) {
return -1;
}
if (n <= node->getKey()) {
return findLargestNumberSmallerThan(node->getLeft(), n);
} else {
int result(findLargestNumberSmallerThan(node->getRight(), n));
if (result == -1) {
result = node->getKey();
}
return result;
}
}
}
{int BST::findLargestNumberSmallerThan(Node * node, int n) {
if (node == NULL) {
return -1;
}
if (n <= node->getKey()) {
return findLargestNumberSmallerThan(node->getLeft(), n);
} else {
int result(findLargestNumberSmallerThan(node->getRight(), n));
if (result == -1) {
result = node->getKey();
}
return result;
}
}
}
- henry.ping March 06, 2011Assume Node A contains the target value if (A is leaf) { the last node we turned right has the value } else { if (A doesn't have left child) { the last node we turned right has the value } else { the right-most child from A's left child has the value) } } TreeNode* g_pLastNodeTurnedRight = NULL; int FindPrevValue(TreeNode* pNode, int nTarget) { if (!pNode) return -1; // -1 indicates not found if (nTarget < pNode->data) { return FindPrevValue(pNode->left, nTarget); } else if (nTarget > pNode->data) { g_pLastNodeTurnedRight = pNode; return FindPrevValue(pNode->right, nTarget); } if (IsLeaf(pNode) || !pNode->left) { return g_pLastNodeTurnedRight ? g_pLastNodeTurnedRight->data : -1; } else { TreeNode* pTmp = pNode->left; while (pTmp) { if (pTmp->right) { pTmp = pTmp->right; } else { break; } } return pTmp->data; } }