Data structures — Trees

Trees are a data structures that link nodes in a parent/child relationship, in the sense that there’re nodes that depend or come off other nodes.

Trees are formed by a root node (the first node on the tree), and all the nodes that come off that root are called children. The nodes at the bottom of the tree, which have no “descendants” are called leaf nodes. And the height of the tree is determined by the amount of parent/child connection it has.

• Root: Top node in a tree.
• Parent: A node that has descendants nodes.
• Child: A node that descends from another node.
• Siblings: nodes that descend from the same parent.
• Leafs: Nodes with no children.
• Edge: The connection of one node with another.

Unlike linked lists or arrays, trees are non linear, in the sense that the program flow can follow different directions within the data structure and hence arrive at different values. While on linked lists or arrays, the program can only iterate the data structure from one extreme of it to the other, always following the same path.

An important requirement for tree formation is that the only valid connection between nodes is from parent to child . Connection between siblings or from child to parent are not allowed in trees (these type of connections form graphs, a different type of data structure). Another important requirement is that trees must have a one and only root.

Some examples of tree usage in programming are:

• The DOM model.
• Situation analysis in artificial intelligence.
• File folders in operating systems.

There’re many different types of trees. In each type of tree, values may be organized following different patterns that make this data structure more suitable to use when facing different kinds of problems.

The most common tree types are:

Binary trees

In binary trees, each node has a maximum of two children. Nodes can’t have more than two children.

Binary search trees (BST)

Binary search trees are just like binary trees but information within them is ordered in away that makes them a suitable data structure for searching. In BST, values are ordered in a way that each node that descends to the left side of its parent must have a value less than its parent, and each node that descends to the right side of its parent must have a value bigger than its parent.

This order in its values make this data structure great for searching, since on every level of the tree we can identify if the value being looked for is greater or less than the parent node, and from that comparison progressively discard roughly half of the data until we reach our value.

When inserting or deleting values, the algorithm will follow the following steps:

• Check if there’s a root node.
• If there is, check if the value to add/delete is greater or less than the node.
• If it is less, check if there is a node to the left and repeat the previous operation. If there’s not, add/remove the node in that position.
• If it is greater, check if there is a node to the right and repeat the previous operation. If there’s not, add/remove the node in that position.

Searching in BST is very similar, only that instead of adding/deleting values we check the nodes for equality with the value we’re looking for.

The big O complexity of these operations is logarithmic (log(n)), though it’s important to recognize that for this complexity to be achieved, the tree must have a balanced structure so that in each search step approximately half of the data can be “discarded”. If more values are stored to one side or another of three, the efficiency of the data structure is affected.

An implementation of a BST might look like this:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }
    find(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
}

Tree traversal

We saw that BST are great for searching values. But how do we search for values in regular trees, where values aren’t in order? In this cases we just need to traverse the tree (check every node within it), and turns out there’re many ways in which we can approach this task.

Breadth first search (BFS)

In breadth first search, each “level” of the tree is progressively checked for the value we’re looking for. The algorithm starts at the root, the goes on to the root’s children, then to the root’s children’s children, and so on until it gets to the last level or “generation” of the tree, scanning the tree in a horizontal way.

The algorithm should follow the following steps:

• Create a queue and a value to store the values of the visited nodes. (Remember that in queue elements are added and removed following a FIFO pattern — First in, first out.)
• Place the root node in the queue
• Loop as long as there’s anything in the queue and: 1) Dequeue a node from the queue and push the node’s value into the variable that stores the visited nodes. 2) If there’s a left property on the dequeued node, add it to the queue. 3) If there’s a right property on the dequeued node, add it to the queue
• Return the variable that stores the values.

A possible implementation could be as following:

BFS(){
        var node = this.root,
            data = [],
            queue = [];
        queue.push(node);
        while(queue.length){
           node = queue.shift();
           data.push(node.value);
           if(node.left) queue.push(node.left);
           if(node.right) queue.push(node.right);
        }
        return data;
    }

Depth first search (DFS)

In depth first search each “branch” of the tree is vertically checked for the value we’re looking for. The algorithm starts at the root, then to one of its children, then to one of its children’s children, and so on until it reaches the leaf level of the branch. Once there, the algorithm backtracks to the first parent node who has an unvisited children and scans through that branch, and repeats the process until the whole tree has been visited.

DFS can be executed in different orders, which will affect the way the tree is traversed.

Example image:

Preorder

In Preorder DFS, the tree wil be traversed following a Root, Left, Right order. Using the tree in the example image, the output would be “1 2 4 5 3”.

An implementation could look as following:

DFSPreOrder(){
        var data = [];
        function traverse(node){
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
}

Post order

In Postorder DFS, the tree wil be traversed following a Left, Right, Root order. Using the tree in the example image, the output would be “4 5 2 3 1”.

An implementation could look as following:

DFSPostOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);
            data.push(node.value);
        }
        traverse(this.root);
        return data;
}

In order

In In order DFS, the tree wil be traversed following a Left, Root, Right order. Using the tree in the example image, the output would be “4 2 5 1 3 “.

An implementation could look as following:

DFSInOrder(){
        var data = [];
        function traverse(node){
            if(node.left) traverse(node.left);
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(this.root);
        return data;
}

Depth first search (DFS) vs Breadth first search (BFS)

How do we choose between DFS and BFS? The difference between them relies only in the use of memory the algorithms will have (space complexity), since the time complexity of both is the same.

Generally speaking, when we have very “wide” trees (trees that have many branches), we will go with DFS; and when we have very “long” trees (trees that have many father-child relationships within each branch) we will go with BFS.

Since BFS traverses trees in a horizontal way, in very wide trees the algorithm will have to use a lot of memories to store all the values of each tree “level”, and the same goes with very long trees and DFS.

Heaps

Heaps are another type of trees that have some particular rules. There are two main types of heaps MaxHeaps and MinHeaps. In MaxHeaps, parent nodes are always greater than its children, and in MinHeaps, parent nodes are always smaller than its children.

In this data structure there’re no guarantees between siblings, meaning that nodes at the same “level” don’t follow any rule besides being higher/lower than its parent. Also, heaps are as compact as possible, meaning each level contains all the nodes it can contain with no empty spaces, and new children are put into the left spaces of the tree first.

Heaps, and in particular binary heaps are frequently used to implement priority queues, which at the same time are frequently used in well known algorithm such as dijkstra’s pathfinding algorithm. Priority queues are a type of data structure in which each element has an associated priority and elements with a higher priority are presented first.

Heaps have a log (n) complexity for insertion and removal operations.