# in-order traversal of a binary search tree c++



## Sphinx (Aug 5, 2003)

I'm trying to right this function, and its almost complete, my only problem is the condition when it hits the largest value in the tree, what should it return?

this is my function prototype;

TreeNode<T>* next_inorder( TreeNode<T>* p );

if the node p has a right node, then it goes all the way left down that right node to find the next in order.

if the node p has no right node, it goes one node up to the left, and then all the way up the right to the find the next in order.

my problems are what about the case where p is the only node in the tree, and what about when p is the last in order node??


----------



## lotuseclat79 (Sep 12, 2003)

Sphinx said:


> I'm trying to right this function, and its almost complete, my only problem is the condition when it hits the largest value in the tree, what should it return?
> 
> this is my function prototype;
> 
> ...


Hi Sphinx,

Each node of a binary tree has a value field and a left and right link field. Given that the binary tree has been created with a prodecure that inserts the value node of the tree in the correct place and correctly links left, and right nodes then the tree is completely ordered, i.e. smallest value at the leftmost node, and largest value at the rightmost node.

A function can then be created to retrieve the max value node's "value", and likewise, a separate function to retrieve the least value node's "value". OTOH, while inserting the "value nodes", the smart thing to do is to construct a header node for the binary tree, with two extra pieces of information in the header node which no value node contains. Those pieces of information are: (min value, ptr to min value node), (max value, ptr to max value node). Saves time on the lookup, and there is then no need to test for max or min on this very fast form of lookup.

An in-order traversal of the tree starts with the pointer to the tree from the header node, and from there visits the first node all of the way to the left, and from that node proceeds right until the last right node is reached which in every case should be the maximum value with a null right pointer. A reverse-order, i.e. max-to-min traversal would start from the max value node all the way to the right, and proceed left to the min value node.

Obviously, a null right node pointer indicates position at the max value node, and likewise, a null left node pointer indicates position at the min value node.

Hope this helps, at least that's how I would design it.

-- Tom


----------

