4 ms·
So I asked him an even simpler question: Given a binary search tree, write code to find a particular value. If you can't find the value, then return me the next
by itmag 15y ago
So I asked him an even simpler question: Given a binary search tree, write code to find a particular value. If you can't find the value, then return me the next smallest value. For example, if the tree contains 1, 2, 3, and 5, and I ask for 4, then return 3.
Out of curiosity, what is the solution?
I would imagine something like keeping a variable of the highest found value under 4 and if you don't find 4 then you use this variable.
- deleted 15y ago[deleted]
- kd5bjo 15y agoStart at the root of the tree; at each node: - If the node value matches, return it - If the node value is too low: - If possible, step right and repeat - Otherwise, return this node value - If the node value is too high: - If possible, step left and repeat - Otherwise, return the value of this node's predecessor: - Walk up until you traverse a right link - Return the node's value - If you hit the root, the requested value is less than any value in the tree
- 3pt14159 15y agoI wrote it out in python for you: http://pastebin.com/5hX9ZMvB http://pastebin.com/5hX9ZMvB and the solution written out in words below, also in python (I like this one better) http://pastebin.com/PapfMhfU http://pastebin.com/PapfMhfU
- deleted 15y ago[deleted]