Tag Archives: binary tree

Disproving Professor Bunyan's hypothesis on Binary search tree

Question (from Introduction to Algorithms by Cormen et al):

Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets: A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to the right of the search path. Professor Bunyan claims that any three keys a ∈ Ab ∈ B, and c ∈ C must satisfy a ≤ b ≤ c. Give a smallest possible counterexample to the professor's claim.

I came across this question and was really wondering how do I find a counter-example to this claim which appeared right for my few initial trees that I made. After a few attempts, I was able to give a counterexample. I would suggest that do try a few more times, before you give up and peek into the solution.

Solution

Non-recursive tree traversal in O(n) using constant space

Question (from Introduction to Algorithms by Cormen et al):

Write an O(n)-time non-recursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

Each node has left, child and parent pointers.

Solution