Trees

There are many different ways to store data in a computer. Arrays store data linearly, which makes them easy to store in a computer, but often you want a different data structure to organize the data in some manner. This module will cover Trees, a data structure that has many different purposes.

This is a tree:

Terms
A Tree contains individual Nodes, such as "2" and "6", and each Node can point to other Nodes, called child nodes. The Node that points to a child Node is called a parent node. The initial Node in the tree has no parent node and is called a Root node, which is "2" in the above tree. Every other Node has just one parent node, and there are no loops in the Tree. The main tree we'll deal with is a Binary Tree, which is a tree where each Node has a maximum of 2 child Nodes.

A Tree is a Tree

Since a computer cannot just store the above Tree directly, we need a way to implement it for a computer. First, let's precisely define a Binary Tree.

A Binary Tree consists of:

• A node, which contains data, and points to:
• 0,1 or 2 sub-trees, which are also binary trees.

So a Tree is just a Node that points to additional Trees. This is a recursively-define data structure, which means we'll be able to use many Recursive Algorithms when dealing with Trees.

Implementing a Tree

To implement a Tree, we'll create a Node class. It will store an integer of Data, and point to 2 child Nodes.

class Node {

    int data;
    Node left;
    Node right;

}

The above code is actually enough for a basic Tree. The initial Node will form the root of the Tree, and other Nodes can be set as it's children. A Tree is just Nodes that point to other Nodes/Trees.

To follow best Java practices, you can make the above fields private and add methods for getting and setting their values. We'll start by adding a constructor and accessor method for data:

class Node {

    private int data;
    Node left;
    Node right;

    public Node(int nodeData){
        data = nodeData;
    }

    public int getData(){
        return data;
    }   

}

You can now create a Tree. For example, this code will create the above Tree with a 2-Node pointing to a 7-Node and a 5-Node:

    Node n1 = new Node(2);      
    Node n2 = new Node(7);
    Node n3 = new Node(5);

    n1.left = n2;
    n1.right = n3;

A Tree in an Array

Computer data is physically stored in a linear manner on hard drives and memory, which means arrays are an optimal representation of data.

It can be more efficient to store other data structures within arrays. To store a Binary Tree in an Array, we just need to determine the order that we store the Nodes in. A good order is "breadth-first" where we store the items in order top-down and left-to-right of the tree.

Here's a tree represented as an array:

And this is the tree 'unfolded':

Notice that 5 only has one child Node, so the other child is represented as 0 in the above array. This is OK as long as we don't need to store actual 0 values.

Challenge

The input for these challenges will provide an array of numbers in the above "breadth-first" format, and use 0's for non-nodes.

Can you print out the sum of the Left-hand side of the Tree?

Tip: A number located at position i in an array will have it's left child located at the position 2i+1 in the array.

You are provided with code that processes the input into an array. If you want to do it yourself, read the input format below.

Input format
The first line of input will contain T, the number of tests cases. T cases will follow, with each case consisting of two lines:

• A number n on the first line
• n numbers follow on the next line.

Sample Input

1
7
2 7 5 2 6 0 9

Sample Output

11

Explanation
Go down the left-hand side of the tree to get the sum: 2+7+2 = 11