Data structures

Question : Write a function to find inorder successor of a given node in a binary  search tree. Our inclination would be to write tree minimum of right subtree. Because we already use this mechanism while deleting a node with both subtrees. But what we fail to notice is that tree minimum of right subtree would be present if there IS a right subtree. What if the node has no right child? What if it is a leaf node? Which nodes are successors of these nodes? And how do we find them? The inorder successor of 3 can be found out as tree minimum of right subtree, which is 4. But what about successors of 4? Or 7? Or successor 13? One method would be to store parent link in each node. And travel up finding parent nodes until the parent node has a value greater than given node. But that needs modification of the structure. Another method is to start from root node and search for a given value and store node with larger value as successor and terminate when we come across a node w...

Question : Write a function to mirror a binary tree. The mirror tree will have a left subtree and right subtree swapped. But this has to be done for each and every node. So to convert a tree to its mirror, we can write an algorithm like this               1) mirror left subtree recursively               2) mirror right subtree recursively               3) swap left and right children of the current node. Here is the function for it. void mirror_tree (NODEPTR root) { if (root != NULL ) { NODEPTR temp = root -> left; root -> left = root -> right; root -> right = temp; mirror_tree(root -> left); mirror_tree(root -> right); } }

Question: How do you find the merge point of two linked lists? Merge point is the first common node of two linked lists. From this node onwards, the lists have same nodes. Note: we are not talking about values in the nodes, but the actual addresses themselves. In the diagram shown, 4 is the merge point of the two lists. You may think that easy solution is traverse two list parallely and compare the respective nodes of the lists. But that does not work. In the diagram shown, if you start with head of list1 and list2, if you compare addresses of 1 and 5, then addresses of 2 and 6, addresses of 3 and 4 and so on, you will never find a match. An easy solution would be  to take one node at a time from first list and compare this with all nodes in second list. Then move on to second node of first list, compare it with all nodes of second list and so on. And continue this process until a match is found. But this process has a complexity of O(n 2 ). Another method will b...

Question : Write a function to test if two binary trees are equal. The trees are equal only if the values are equal and also the structures are equal. Equal trees       89                                89   12      100                    12       100 2                                 2 Not equal trees         89                          ...