Trees


Collapse Content

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:

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.

simple tree

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.

binary tree in array

Here's a tree represented as an array:
binary tree in array with data

And this is the tree 'unfolded':
tree as tree

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

Challenge

A sibling node is a Node that shares a parent with a given node. What's the Sibling of "11" in the above tree?

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Challenge

Print out the sum of the left-hand side of the array-tree, as above.

Please sign in or sign up to submit answers.

Alternatively, you can try out Learneroo before signing up.

Comments

  • If it is best practice to make the node value private why isn't it best practice to make the children nodes private and require methods to access them?

  • It may be "better practice" to do that for the Nodes as well, but its simpler to do these algorithms without creating getters and setters for the Node's children.

  • I try to use this code https://www.learneroo.com/user_answers/7605767388

    but I get back "Main.java:11: error: non-static variable this cannot be referenced from a static context Node node = new Node(ar[i]);"

    I am going crazy. Where is the problem?

  • @Salvatore, looking briefly at your code, you should move your Node class out of the Main class (though you'll still have some more work to do).

    public class Main{
      //all of class Main
    }
    
    class Node{
      //all of class Node
    }
    
  • Ops, thanks! Meanwhile I figured it out by myself.

    And I am still fighting to find the solution. Keep (all of) you posted!

Contact Us
Sign in or email us at [email protected]