Tree Intro

In comparison to other data structures, trees can be a little difficult to grasp.

The simpler data structures intuitively make sense after some experience. For instance, when first working with arrays, manipulating strings or character arrays, you may be able to anticipate the results. In contrast, setting up your tree data structure can be confusing.

What will we do?

Let us see if we can use recursion to iterate over a tree data structure, sum the values, and store each sum in a list.

Let us start with a basic environment.

Prereqs

• Code editor (VS Code)
• Unit Testing tool (xUnit)
• .Net Sdk

If you plan to follow along, please use the same tools above - although any tool you choose can work equally as well.

Download/Install the following:

• VS Code
• xUnit
• .NET SDK

The Commands

Create a directory and navigate to the directory

   $ mkdir /c/Projects/Learn/TestATree && cd /c/Projects/Learn/TestATree 

Create a xUnit project within the directory

   $ dotnet new xUnit

Your directory should contain the following files and folders:

   obj/  TestATree.csproj  UnitTest1.cs  Usings.cs

Run the xUnit tests

$ dotnet test
  Determining projects to restore...
  All projects are up to date for restore.
  TestATree -> C:\Projects\Learn\TestATree\bin\Debug\net6.0\TestATree.dll
Test run for C:\Projects\Learn\TestATree\bin\Debug\net6.0\TestATree.dll (.NETCoreApp,Version=v6.0)
Microsoft (R) Test Execution Command Line Tool Version 17.3.0 (x64)
Copyright (c) Microsoft Corporation.  All rights reserved.

Starting test execution, please wait...
A total of 1 test files matched the specified pattern.

Passed!  - Failed:     0, Passed:     1, Skipped:     0, Total:     1, Duration: < 1 ms - TestATree.dll (net6.0)

Open your directory in your code editor (VS Code)

$ code .

The Data Structure

The BinaryTree class is the blueprint of the node object used in the calculation:

    public class BinaryTree
    {
        public int value;
        public BinaryTree left;
        public BinaryTree right;

        public BinaryTree(int value)
        {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

In the above, each bainaryTree object will have a left pointer (to another node) as well as a right pointer (to another node). And all BinaryTree nodes are instantiated with a value.

The Algorithm

tldr: Using recursion, traverse a tree and sum the values.

 public static List<int> BranchSums(BinaryTree root)
    {
        List<int> sums = new List<int>();
        CalculateBranchSums(root, 0, sums);
        return sums;
    }

    private static void CalculateBranchSums(BinaryTree node, int runningSum, List<int> sums)
    {
        if (node == null) return;

        int newRunningSum = runningSum + node.value;
        if (node.left == null && node.right == null)
        {
            sums.Add(newRunningSum);
            return;
        }
        CalculateBranchSums(node.left, newRunningSum, sums);
        CalculateBranchSums(node.right, newRunningSum, sums);
    }

The above code utilizes a list data structure and recursion. The tricky part is CalculateBranchSums(node.left, newRunningSum, sums).

So, what is happening?

The BranchSums method takes in a BinaryTree root object and passes it to a recursion method CalculateBranchSums(root, 0, sums); and finally returns the sum of the binary tree stored in a list.

CalculateBranchSums(root, 0, sums); takes in the root object, starts with a running sum of 0 with an empty sum list to hold the final values.

Since the method is recursive, we need a base case:

if (node == null) return;

Outside of the base case, the running sum is added to the value of the visited node and stored in newRunningSum.

Then we iterate over the tree by visiting each node and checking if the visited node has a left and right leaf pointing to null leaves (null means we are at the end of a tree since each node should point to another node).

Let us create our unit test of the binary tree. Within your UnitTest1, copy and paste the following:

   public class UnitTest1
    {
        [Fact()]
        public void MainTest()
        {

            //arrange
            BinaryTree root = new BinaryTree(1);
            root.left = new BinaryTree(2);
            root.right = new BinaryTree(3);

            root.left.left = new BinaryTree(4);
            root.left.right = new BinaryTree(5);
            root.right.left = new BinaryTree(6);
            root.right.right = new BinaryTree(7);

            root.left.left.left = new BinaryTree(8);
            root.left.left.right = new BinaryTree(9);
            root.left.right.left = new BinaryTree(10);

            List<int> actualList = new List<int>()
            {
                15, 16, 18, 10, 11
            };

            //act
            List<int> sumList = Program.BranchSums(root);
  
            //assert
            Assert.Equal(sumList, actualList);

        }
    }

The above code uses the 3A Pattern (Arrange-Act-Assert). There are other patterns so feel free to use the one that you feel comfortable with.

• Arrange
  • instantiate the BinaryTree root class and subsequent nodes
• Act
  • Call the BranchSums method
• Assert
  • Test the assertion of the actual and the sum

Summary

We covered iterating over a tree data structure. Summing the values of a binary tree and returning a list of the sums. We also touched a little on recursion and unit testing.

• web development