Ternary Search Tree Java

Problem

Write a java program to construct and print a ternary Tree. A ternary tree is similar to a binary tree except a parent node can have up to three children instead of two. The left child value is less than the parent value, the right is greater than the parent value and the middle value is equal to the parent value.

Solution

We need to have a Node data structure that has three child nodes and one value. Populating and printing the tree can be achieved using recursive calls. For more details you can take a look at the commented source code below.

Code

Here is the code in Java

//Main class
public class TrinaryTree 
{
    //Main function
    public static void main(String[] args) 
    {
         //Sample tree values rooted at 5
         int Values[] = {5, 4, 9, 5, 7, 2, 2};
         
         //Create Tree
         TrinaryTree tree = new TrinaryTree();
         
         //Populate tree
         tree.Populate(Values, 7);
    }
    
    //Define a tree node
    static class Node
    {
        //Left is less than node value
        Node left;
        //Middle is equal to node value
        Node middle;
        //Right is greater than node value
        Node right;
        
        //Node value
        int value;

        //Constructor
        public Node(int value) 
        {
            this.value = value;
        }
    }

    //Populate method: receives an
    //array of integers along with
    //its size (n)
    public void Populate(int A[], int n) 
    {
        //Tree rooted at the first
        //element of the array
        Node root = new Node(A[0]);
        
        //Insert values into the tree
        for (int i = 1; i < n; i++)
        {
             Insert(root, A[i]);
        }

        //Print tree
        Print(root);
    }

    //Insert a node into the tree
    public void Insert(Node node, int value) 
    {         
        //If the value to be inserted
        //is less than node value then
        //we either inserts it as the 
        //left child if it does not exist 
        //or recursively call the insert 
        //on the left child if it does exist
        if (value < node.value) 
        {
            //Left child exist
            if (node.left != null) 
            {
                Insert(node.left, value);
            } 
            //Left child does not exist
            //so create it
            else 
            {
                node.left = new Node(value);
            }
        } 
        //Same reasoning as above but for right
        else if (value > node.value) 
        {
            if (node.right != null) 
            {
                Insert(node.right, value);
            } 
            else 
            {
                node.right = new Node(value);
            }
        }
        //Same reasoning as above but for middle
        else
        {
            if (node.middle != null) 
            {
                Insert(node.middle, value);
            } 
            else 
            {
                node.middle = new Node(value);
            }
        }
    }

    //Recursive method to print the
    //whole tree
    public void Print(Node root) 
    {
        if (root != null) 
        {
            System.out.println("Node value : " + root.value);
            Print(root.left);
            Print(root.middle);            
            Print(root.right);
        }
    }
}
Search Terms...

Comments are closed.

%d bloggers like this: