inorder successor

Problem : Given a Binary tree where each node has an extra field (node * next), write a function that puts the inorder successor of that node in the next pointer. This is how our binary tree node looks like : struct node { int data; struct node\* left; struct node\* right; struct node\* next; } Initially, all next pointers have NULL values. Your function should fill these next pointers so that they point to inorder successor. [Read More]

Since traversing the three is the most frequent operation, a method must be devised to improve the speed. In case of iterative traversal, speed is less than recursive one. So we cans use Threaded tree. If the right link of a node in a tree is NULL, it can be replaced by the address of its inorder successor. This tree is called right in-threaded binary tree. An extra field called the rthread is used. [Read More]

It is important to understand inorder successor of BST because it helps us understand deletion of node from a tree, when the node deleted has 2 children. To find the inorder successor of node u: If u has a right child, r, then succ(u) is the leftmost descendent of r Otherwise, succ(u) is the closest ancestor, v, of u (if any) such that u is descended from the left child of v. [Read More]