The next question I received quite a bit was how do you search for elements in a binary tree. Thank goodness I paid attention in CS225.
Straight from the book… A binary tree is a hierarchical structure of nodes, each node referencing at most to two child nodes. Every binary tree has a root from which the first two child nodes originate. If a node has no children, then such nodes are usually termed leaves, and mark the extent of the tree structure. A particular kind of binary tree, called the binary search tree, is very useful for storing data for rapid access, storage, and deletion. Data in a binary search tree is stored in tree nodes, and must have associated with them an ordinal value or key; these keys are used to structure the tree such that the value of a left child node is less than that of the parent node, and the value of a right child node is greater than that of the parent node. So with that, let’s dive into the code.
There are two ways you can find a key in a binary tree, recursively and iteration with a while loop. Since most places allow you to do pseudocode, I’ll keep my answers short and sweet.
Recursion
Node Search(Node, key)
{
if Node = NIL or key = Node.key
return Node
if key < Node.key
then return Search(Node.Left, key)
else return Search(Node.Right, key)
}
While Loop
Node Search(key)
{
Node = root
while Node != NIL and key != Node.key
do if key < Node.key
then Node = Node.Left
else Node = Node.Right
return Node
}
I’ve realized after going through a few of these interviews that if you solve a problem using an iterative function, they’ll most likely ask you to solve it using recursion as well, so make sure you understand the basics of recursion. Thanks for reading this post. I hope it proves useful to you in your job hunt.
-DeVaris
