Find root from any node in a BST

Question

How can I find the root of a binary search tree from any given node? More specifically, when should I stop while going through the ancestors from any given node? Is there any function in java to get the root? Please help me.

Answer 1

I'm assuming you are writing your own BST implementation in Java or something among those lines? If the nodes store a reference to the parent node, eventually you'll encounter a node that has null for parent while climbing up the tree. This node should normally be the root.

If your nodes store no such reference, there is no way to get to the root if all you have is a single node. Many implementations lack references to parent nodes, because it saves memory and can be taken care of by using a stack while traversing the tree (for a depth-first traversal).

But it is unclear to me what exactly you're trying to do. Why do you need to find the root node?

Answer 2

Here is a binary tree node representation in java

class Node{
    int data;
    Node leftChild;
    Node rightChild;
}

But, if we follow this kind of node representation then it'd hard to traverse from leaf nodes to their ancestors. This kind of representation is fit for the problems in which reference to the root node is given along with the problem statement.

In order to start traversing from a node at any position in the tree, we have to put a reference to the parent in the node class.

class Node{
    int data;
    Node parent;
    Node leftChild;
    Node rightChild;
}

Now if you start traversing you must stop when you find a null parent for a node.

/* the logic for traversing */
Node tempRoot = given node;
while(true){
    if(null != tempRoot.parent){
        tempRoot = tempRoot.parent;

    }else{
        break;
    }
}
/* return value of tempRoot: this is your root */

[Edit: I have omitted getters and setters. Though I am not suggesting to implement like this :) ]

Answer 3

If you have implemented your own BST, then you should have a data member Node root; in your BST class, you can access/find the root by simply accessing that data member from any method of BST class