Mixing
Find largest smaller key in Binary Search Tree
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Given a root of a Binary Search Tree (BST) and a number num, implement
an efficient function findLargestSmallerKey that finds the largest key
in the tree that is smaller than num. If such a number doesn’t exist,
return -1. Assume that all keys in the tree are nonnegative.
The Bst Class is given to me.
public class BstNode
public int key;
public BstNode left;
public BstNode right;
public BstNode parent;
public BstNode(int keyt)
key = keyt;
you can ignore the unit test code this is a just the demo.
[TestMethod]
public void LargestSmallerKeyBstRecrussionTest()
BstNode root = new BstNode(20);
var left0 = new BstNode(9);
var left1 = new BstNode(5);
var right1 = new BstNode(12);
right1.left = new BstNode(11);
right1.right = new BstNode(14);
left0.right = right1;
left0.left = left1;
var right0 = new BstNode(25);
root.right = right0;
root.left = left0;
Assert.AreEqual(14, helper.FindLargestSmallerKeyRecursion(17, root));
this is the code I would like you please to review, comment.
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
if (root.key < num)
return Math.Max(root.key, temp);
return temp;
c# interview-questions binary-search
asked 4 hours ago
Gilad
1,19221226
 |Â
show 1 more comment
up vote
2
down vote
favorite
Given a root of a Binary Search Tree (BST) and a number num, implement
an efficient function findLargestSmallerKey that finds the largest key
in the tree that is smaller than num. If such a number doesn’t exist,
return -1. Assume that all keys in the tree are nonnegative.
The Bst Class is given to me.
public class BstNode
public int key;
public BstNode left;
public BstNode right;
public BstNode parent;
public BstNode(int keyt)
key = keyt;
you can ignore the unit test code this is a just the demo.
[TestMethod]
public void LargestSmallerKeyBstRecrussionTest()
BstNode root = new BstNode(20);
var left0 = new BstNode(9);
var left1 = new BstNode(5);
var right1 = new BstNode(12);
right1.left = new BstNode(11);
right1.right = new BstNode(14);
left0.right = right1;
left0.left = left1;
var right0 = new BstNode(25);
root.right = right0;
root.left = left0;
Assert.AreEqual(14, helper.FindLargestSmallerKeyRecursion(17, root));
this is the code I would like you please to review, comment.
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
if (root.key < num)
return Math.Max(root.key, temp);
return temp;
c# interview-questions binary-search
asked 4 hours ago
Gilad
1,19221226
This can crash ifroot.left == nullbutroot.right != null. Example:BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(5, root);
– Martin R
3 hours ago
AndBstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(15, root);does not find 10 as the largest key which is less than 15, but returns -1 instead.
– Martin R
3 hours ago
2
Thanks! I Will fix it!
– Gilad
3 hours ago
@MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
– Gilad
1 hour ago
The first problem was “obvious,†you handled only the cases where both subtrees are null, or none of them. – Then your initial solution “looked too symmetric†and I just played with the most simple examples.
– Martin R
38 mins ago
 |Â
show 1 more comment
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Given a root of a Binary Search Tree (BST) and a number num, implement
an efficient function findLargestSmallerKey that finds the largest key
in the tree that is smaller than num. If such a number doesn’t exist,
return -1. Assume that all keys in the tree are nonnegative.
The Bst Class is given to me.
public class BstNode
public int key;
public BstNode left;
public BstNode right;
public BstNode parent;
public BstNode(int keyt)
key = keyt;
you can ignore the unit test code this is a just the demo.
[TestMethod]
public void LargestSmallerKeyBstRecrussionTest()
BstNode root = new BstNode(20);
var left0 = new BstNode(9);
var left1 = new BstNode(5);
var right1 = new BstNode(12);
right1.left = new BstNode(11);
right1.right = new BstNode(14);
left0.right = right1;
left0.left = left1;
var right0 = new BstNode(25);
root.right = right0;
root.left = left0;
Assert.AreEqual(14, helper.FindLargestSmallerKeyRecursion(17, root));
this is the code I would like you please to review, comment.
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
if (root.key < num)
return Math.Max(root.key, temp);
return temp;
c# interview-questions binary-search
asked 4 hours ago
Gilad
1,19221226
Given a root of a Binary Search Tree (BST) and a number num, implement
an efficient function findLargestSmallerKey that finds the largest key
in the tree that is smaller than num. If such a number doesn’t exist,
return -1. Assume that all keys in the tree are nonnegative.
The Bst Class is given to me.
public class BstNode
public int key;
public BstNode left;
public BstNode right;
public BstNode parent;
public BstNode(int keyt)
key = keyt;
you can ignore the unit test code this is a just the demo.
[TestMethod]
public void LargestSmallerKeyBstRecrussionTest()
BstNode root = new BstNode(20);
var left0 = new BstNode(9);
var left1 = new BstNode(5);
var right1 = new BstNode(12);
right1.left = new BstNode(11);
right1.right = new BstNode(14);
left0.right = right1;
left0.left = left1;
var right0 = new BstNode(25);
root.right = right0;
root.left = left0;
Assert.AreEqual(14, helper.FindLargestSmallerKeyRecursion(17, root));
this is the code I would like you please to review, comment.
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
if (root.key < num)
return Math.Max(root.key, temp);
return temp;
c# interview-questions binary-search
c# interview-questions binary-search
asked 4 hours ago
Gilad
1,19221226
asked 4 hours ago
Gilad
1,19221226
edited 1 hour ago
asked 4 hours ago
Gilad
1,19221226
asked 4 hours ago
Gilad
1,19221226
asked 4 hours ago
Gilad
1,19221226
1,19221226
This can crash ifroot.left == nullbutroot.right != null. Example:BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(5, root);
– Martin R
3 hours ago
AndBstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(15, root);does not find 10 as the largest key which is less than 15, but returns -1 instead.
– Martin R
3 hours ago
2
Thanks! I Will fix it!
– Gilad
3 hours ago
@MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
– Gilad
1 hour ago
The first problem was “obvious,†you handled only the cases where both subtrees are null, or none of them. – Then your initial solution “looked too symmetric†and I just played with the most simple examples.
– Martin R
38 mins ago
 |Â
show 1 more comment
This can crash ifroot.left == nullbutroot.right != null. Example:BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(5, root);
– Martin R
3 hours ago
AndBstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(15, root);does not find 10 as the largest key which is less than 15, but returns -1 instead.
– Martin R
3 hours ago
2
Thanks! I Will fix it!
– Gilad
3 hours ago
@MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
– Gilad
1 hour ago
The first problem was “obvious,†you handled only the cases where both subtrees are null, or none of them. – Then your initial solution “looked too symmetric†and I just played with the most simple examples.
– Martin R
38 mins ago
This can crash if
root.left == null but root.right != null. Example: BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(5, root);– Martin R
3 hours ago
This can crash if
root.left == null but root.right != null. Example: BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(5, root);– Martin R
3 hours ago
And
BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(15, root); does not find 10 as the largest key which is less than 15, but returns -1 instead.– Martin R
3 hours ago
And
BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(15, root); does not find 10 as the largest key which is less than 15, but returns -1 instead.– Martin R
3 hours ago
2
2
Thanks! I Will fix it!
– Gilad
3 hours ago
Thanks! I Will fix it!
– Gilad
3 hours ago
@MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
– Gilad
1 hour ago
@MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
– Gilad
1 hour ago
The first problem was “obvious,†you handled only the cases where both subtrees are null, or none of them. – Then your initial solution “looked too symmetric†and I just played with the most simple examples.
– Martin R
38 mins ago
The first problem was “obvious,†you handled only the cases where both subtrees are null, or none of them. – Then your initial solution “looked too symmetric†and I just played with the most simple examples.
– Martin R
38 mins ago
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
3
down vote
Your code works correctly now (as far as I can tell). But due to
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
it always traverses the entire tree. This can be improved:
- If
root.key < numthenroot.keyis a possible candidate for the result,
better candidates can only exist in the right subtree. - Otherwise, if
root.key >= num, keys less than the given bound can only
exist in the left subtree.
That leads to the following implementation:
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
else if (root.key < num)
int tmp = FindLargestSmallerKey(num, root.right);
return tmp != -1 ? tmp : root.key;
else
return FindLargestSmallerKey(num, root.left);
This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the height of
the tree. If the tree is balanced then the result is found in $ O(log N) $
time where $ N $ is the number of nodes.
The same idea can be used for an iterative solution:
public static int FindLargestSmallerKey(uint num, BstNode root)
int result = -1;
while (root != null)
if (root.key < num)
// root.key is a candidate, continue in right subtree:
result = root.key;
root = root.right;
else
// root.key is not a candidate, continue in left subtree:
root = root.left;
return result;
answered 54 mins ago
Martin R
14.7k12259
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. TheMath.Maxis not needed, since search in right subtree either returns a better result, or-1.
– Martin R
41 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
Your code works correctly now (as far as I can tell). But due to
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
it always traverses the entire tree. This can be improved:
- If
root.key < numthenroot.keyis a possible candidate for the result,
better candidates can only exist in the right subtree. - Otherwise, if
root.key >= num, keys less than the given bound can only
exist in the left subtree.
That leads to the following implementation:
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
else if (root.key < num)
int tmp = FindLargestSmallerKey(num, root.right);
return tmp != -1 ? tmp : root.key;
else
return FindLargestSmallerKey(num, root.left);
This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the height of
the tree. If the tree is balanced then the result is found in $ O(log N) $
time where $ N $ is the number of nodes.
The same idea can be used for an iterative solution:
public static int FindLargestSmallerKey(uint num, BstNode root)
int result = -1;
while (root != null)
if (root.key < num)
// root.key is a candidate, continue in right subtree:
result = root.key;
root = root.right;
else
// root.key is not a candidate, continue in left subtree:
root = root.left;
return result;
answered 54 mins ago
Martin R
14.7k12259
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. TheMath.Maxis not needed, since search in right subtree either returns a better result, or-1.
– Martin R
41 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
add a comment |Â
up vote
3
down vote
Your code works correctly now (as far as I can tell). But due to
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
it always traverses the entire tree. This can be improved:
- If
root.key < numthenroot.keyis a possible candidate for the result,
better candidates can only exist in the right subtree. - Otherwise, if
root.key >= num, keys less than the given bound can only
exist in the left subtree.
That leads to the following implementation:
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
else if (root.key < num)
int tmp = FindLargestSmallerKey(num, root.right);
return tmp != -1 ? tmp : root.key;
else
return FindLargestSmallerKey(num, root.left);
This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the height of
the tree. If the tree is balanced then the result is found in $ O(log N) $
time where $ N $ is the number of nodes.
The same idea can be used for an iterative solution:
public static int FindLargestSmallerKey(uint num, BstNode root)
int result = -1;
while (root != null)
if (root.key < num)
// root.key is a candidate, continue in right subtree:
result = root.key;
root = root.right;
else
// root.key is not a candidate, continue in left subtree:
root = root.left;
return result;
answered 54 mins ago
Martin R
14.7k12259
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. TheMath.Maxis not needed, since search in right subtree either returns a better result, or-1.
– Martin R
41 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
add a comment |Â
up vote
3
down vote
up vote
3
down vote
Your code works correctly now (as far as I can tell). But due to
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
it always traverses the entire tree. This can be improved:
- If
root.key < numthenroot.keyis a possible candidate for the result,
better candidates can only exist in the right subtree. - Otherwise, if
root.key >= num, keys less than the given bound can only
exist in the left subtree.
That leads to the following implementation:
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
else if (root.key < num)
int tmp = FindLargestSmallerKey(num, root.right);
return tmp != -1 ? tmp : root.key;
else
return FindLargestSmallerKey(num, root.left);
This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the height of
the tree. If the tree is balanced then the result is found in $ O(log N) $
time where $ N $ is the number of nodes.
The same idea can be used for an iterative solution:
public static int FindLargestSmallerKey(uint num, BstNode root)
int result = -1;
while (root != null)
if (root.key < num)
// root.key is a candidate, continue in right subtree:
result = root.key;
root = root.right;
else
// root.key is not a candidate, continue in left subtree:
root = root.left;
return result;
answered 54 mins ago
Martin R
14.7k12259
Your code works correctly now (as far as I can tell). But due to
int temp = Math.Max( FindLargestSmallerKey(num, root.left), FindLargestSmallerKey(num, root.right));
it always traverses the entire tree. This can be improved:
- If
root.key < numthenroot.keyis a possible candidate for the result,
better candidates can only exist in the right subtree. - Otherwise, if
root.key >= num, keys less than the given bound can only
exist in the left subtree.
That leads to the following implementation:
public static int FindLargestSmallerKey(uint num, BstNode root)
if (root == null)
return -1;
else if (root.key < num)
int tmp = FindLargestSmallerKey(num, root.right);
return tmp != -1 ? tmp : root.key;
else
return FindLargestSmallerKey(num, root.left);
This is faster because at each step, only one subtree is inspected instead of both, so that the time complexity is limited by the height of
the tree. If the tree is balanced then the result is found in $ O(log N) $
time where $ N $ is the number of nodes.
The same idea can be used for an iterative solution:
public static int FindLargestSmallerKey(uint num, BstNode root)
int result = -1;
while (root != null)
if (root.key < num)
// root.key is a candidate, continue in right subtree:
result = root.key;
root = root.right;
else
// root.key is not a candidate, continue in left subtree:
root = root.left;
return result;
answered 54 mins ago
Martin R
14.7k12259
edited 47 mins ago
answered 54 mins ago
Martin R
14.7k12259
answered 54 mins ago
Martin R
14.7k12259
answered 54 mins ago
Martin R
14.7k12259
14.7k12259
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. TheMath.Maxis not needed, since search in right subtree either returns a better result, or-1.
– Martin R
41 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
add a comment |Â
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. TheMath.Maxis not needed, since search in right subtree either returns a better result, or-1.
– Martin R
41 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
yes I did the iterative way first, but I am having a hard time with converting to recursion. so I tried...
– Gilad
50 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. The
Math.Max is not needed, since search in right subtree either returns a better result, or -1.– Martin R
41 mins ago
@Gilad: I have rewritten the recursive solution slightly, so that it resembles the iterative version more closely. The
Math.Max is not needed, since search in right subtree either returns a better result, or -1.– Martin R
41 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
Yes. I used max to solve that issue but in general you are right.
– Gilad
26 mins ago
add a comment |Â
Â
draft saved
draft discarded
Â
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f204105%2ffind-largest-smaller-key-in-binary-search-tree%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
This can crash if
root.left == nullbutroot.right != null. Example:BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(5, root);– Martin R
3 hours ago
And
BstNode root = new BstNode(10); root.right = new BstNode(20); int x = FindLargestSmallerKey(15, root);does not find 10 as the largest key which is less than 15, but returns -1 instead.– Martin R
3 hours ago
2
Thanks! I Will fix it!
– Gilad
3 hours ago
@MartinR Hey I changed the code and fixed the issues I had, I seem to have a hard time with those type of questions. can you please explain how do you look at those type of questions? how do you find all of the edge cases? thanks!
– Gilad
1 hour ago
The first problem was “obvious,†you handled only the cases where both subtrees are null, or none of them. – Then your initial solution “looked too symmetric†and I just played with the most simple examples.
– Martin R
38 mins ago