Trees

Trees are another well known data structure. Again, they use the Node object and basically, a tree node will always one root node that has a link to 2 other nodes (usually left and right) and then when the tree grows in size, the left or right nodes become parent nodes. To illustrate:

So in the diagram(s) above, we see that there will always be one node that acts as the root node (a node that is considered to be the starting point, so no parent nodes for the root) to the child nodes (left and right), and when there are more items added onto the tree, those child nodes becomes parent nodes and so forth. They can have a reference to either 1 child node or two. These are called binary trees. There's other kinds of trees, but for now, we will focus on this kind, as they are most commonly used.

Trees are useful in that you can use them to create a mock system directory/folder hierarchy of sorts. Or you just use them to sort your data out. Printing a tree structure requires some recursion because we want to access all the nodes of the tree, so going up and down the tree requires it. Best case scenario, they have O(log(n)) complexity when you're doing searching through a binary tree.

My implementation in C# (again you can use the same code in Java):

    class TreeNode
    {
        public int data;
        public TreeNode left { get; set; }
        public TreeNode right { get; set; }
       
        public TreeNode(int data)
        {
            this.data = data;
        }
    }
    class Tree
    {
        public TreeNode root;//this is public so we can access this treenode from main when we display our tree using the recursive function

        private int itemCount;
        public Tree()
        {
            root = null;
            itemCount = 0;
        }
        public void insert(int data)
        {
            TreeNode newItem = new TreeNode(data);//our new node to insert into the tree
            if (root == null)//if theres no root, make the first new node the root
            {
                root = newItem;
            }
            else
            {
                TreeNode current = root;//we make a new treenode called current and assign to the root, so we start iteration from there

                TreeNode parent = null;
                while (current != null)//while the current is not equal to null (since we have it equal to root)
                {
                    parent = current;//set the parent node to point to current (which the root treenode, which will be the parent to the new item treenode)

                    if (data < current.data)
                    //if new item (data) is less than the current node's data, link it to the left node
                    {
                        current = current.left;
                        if (current == null)//if the current.left is null
                        {
                            parent.left = newItem;//make parent.left store the new node
                        }
                    }
                    else
                    {
                        current = current.right;
                        if (current == null)
                        {
                            parent.right = newItem;
                        }
                    }
                    itemCount++;
                }
            }
        }
        public void InOrderRecursiveTreeDisplay(TreeNode root)
        {
            if (root != null)
            {
                InOrderRecursiveTreeDisplay(root.left);
                Console.Write("({0})", root.data);
                InOrderRecursiveTreeDisplay(root.right);
            }
        }
        public bool RecursiveFindValue(TreeNode root, int data)
        {
            if (root != null)
            {
                RecursiveFindValue(root.left, data);
                RecursiveFindValue(root.right, data);
                if (root.data == data)
                {
                    Console.WriteLine("Value exists!");
                    return true;
                }
            }
            return false;
        }
    }
class Program
    {
        static void Main()
        {

            Tree t = new Tree();

            t.insert(5);
            t.insert(3);
            t.insert(9);
            t.insert(1);
            t.insert(4);
            t.insert(8);
            t.insert(10);

            Console.WriteLine("\nTree (inorder)");
            t.InOrderRecursiveTreeDisplay(t.root);
            Console.WriteLine();
            t.RecursiveFindValue(t.root, 1);

            Console.ReadLine();
}