Exploring a binary search tree

Question

I figure a binary search tree is the simplest example, but really I would like to know how to explore a ternary search tree or some variety of tries. I don't have any experience with these, but I understand the concepts of adding to and searching them.

My question is, when I find a node that matches my input (like for autocomplete) how do I effectively gather all of the child nodes?

Answer 1

It depends on the implementation of your search tree. If obtaining all of the child nodes of a specific node is a common operation you need to perform, you should use an implementation that makes that operation efficient.

For example, for each node you could store a children array which contains pointers to each of the node's children.

Answer 2

For a Trie, you should have Node structure as

class Node  
{
    char data;
    ArrayList<Node> children;

    public Node getChild(char data)
    {
        for(Node child : this.children)
            if(child.data == data)
               return child;
        return null;
    }
}

Each Node will contain a character and List of its children node
So your searching will loook something like this

public boolean search(String s)
{
    Node current = root;         // root is the Node present in Trie
    for(int i=0; i<s.length(); i++)
    {
       char c = s.charAt(i);
       Node n = current.getChild(c);
       if(n==null)
           return false;   // Match not present
       current = n;
    }
    return true;       // Match found
}

The above search method just checks whether the searched string is present in your trie. You can tweak it to gather all the children as per your requirement (That is kept for you :) )

Hope this helps you and give you an idea how to gather it. If need any assistance in populating trie. Let us know!

NOTE In Trie node you can also maintain a boolean marker to indicate the end of a word. You may use or do not use it depending upon your application and usage.