class Node
public Node Right;
public Node Left;
public int Key;
public String Value;

Write a function which will search a given BST for a specific key and return a Value for the found node for the tree defined above.

This algorithm is quite simple. We begin by checking the key from the root node. If the root is null it either means the null node was passed to the function or we reached a leaf and have not found the key, which means the key is not in the tree at all.  If the key is less than the root, then it must be in the left sub-tree, so we recursively call FindBSTNode for the left sub-tree key. Similarly, if the key is greater than the root, then it must be in the right sub-tree, so we recursively search the right part of the tree. If at some point the key we are searching for equals the root, it means we have found the node. Execution time for this algorithm is O(n) for the worst case scenario and comes to O(log2 n) for the well balanced tree.

C# Solution:

public static string FindBSTNode(Node root, int key) { if (root == null) return null; string result; if (key < root.Key) result = FindBSTNode(root.Left, key); else if (key > root.Key) result = FindBSTNode(root.Right, key); else result = root.Value; return result; }

Answers and Comments