Working With Trees

8 min readJan 10, 2019

Trees are a hierarchical data structure in computer science where the data is structured in a parent / child relationship. Understanding the tree data structure is important because we interact with it often — whether that be in our files systems, working with the DOM or in creating smart AI systems.

In this article, I’ll go over the basics of the tree data structure, including how to implement and traverse a tree and different searching algorithms based off the type of tree data you’re working with.

A Tree

First, let’s make sure we’re on the same page. The image below shows a set of numbers represented in a tree data structure.

Tree Terminology

When working with a tree data structure, the following verbiage is helpful to know.

Nodes: Nodes store your data’s value, whether that be numbers, strings etc
Root: The root node is the first node in the tree. In the above example, the root node is 2.
Child: A node that is directly connected to another node that is further away from the root node.
Parent: The inverse of a child
Siblings: A group of nodes that share the same parent. In the above example 9,12,8,99,10 are all siblings.
Leaf: Is a node with no children. In the above, 2 is an example of a leaf node.

Binary Trees

There are many subsets of trees, one being binary trees. A binary tree is when each node can have at most two child nodes. In a binary tree, the data is not sorted in any particular way. A sorted binary tree is known as a binary search tree or BST for short. BSTs are great for retrieving stored data. The image below is an example of a BST.

The algorithm for how to build a BST is pretty straightforward. Given a new value you start at the root node. You ask, is this new value greater than or less than the current node value. If it is greater you move right and if it is less than you move left. You repeat this process until you find a node with an empty child position and then place your new value there.

Given the below BST, imagine we wanted to insert a new value of 13.

*A note on duplicates. Given the logic for BSTs, every key in a BST should be unique. If duplicate keys are needed, then creating a counter function of each node to denote duplicates is the preferred approach.

Binary Search Tree Pseudocode (For Insertion and Finding)

Create a new node
Start at the root node
Check if there is a root node, if not set it as the new node and return
If there is a root node, check if the new value is greater than or less than
If greater: move right. If there is no node, set the new node. If there is a node, compare and move left or right.
If less then: move left. If there is no left node, set the new node. If there is a node, compare and move left or right.

*I’ve written out pseudocode for inserting a new node, however to find a node, the logic remains almost identical, except that instead of setting a new node you check to see if the given value is the same as the node you are on and if yes, you return the node.

Implementation Code

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}class BST {
    constructor(){
        this.root = null;
    }    insert(value, node=this.root){
        let newNode = new Node(value)
        if (node === null){
            this.root = newNode
            return this;
        }        if (newNode.value === node.value) return undefined        if (newNode.value > node.value) {
            if (node.right === null) {
                node.right = newNode
            } else {
                node = node.right
                this.insert(newNode.value, node)
            }
         } else {
            if (node.left === null) {
                node.left = newNode
            } else {
                node = node.left
                this.insert(newNode.value, node)
            }
         }
     
         return this;
    }    find(value, node=this.root){
        if (!node) return false
        if (value === node.value) return node
                
        if (value > node.value) {
            if (!node.right) return false
            return this.find(value, node = node.right)   
        } else {
            if (!node.left) return false
            return this.find(value, node = node.left)
        }
    }}

Big O Complexity of Binary Search Trees

The time complexity for a BST on average is O(log n). The reason for this is that every time we move on to another child node, we are effectively cutting the data set in half. Now, if our root node is either near the minimum or the maximum in the dataset, then our time efficiency gets much worse and becomes O(n) as we end up searching every value in the tree.

Here is an example of a poorly constructed BST where the worst case scenario is realized.

Binary Search Tree Searching Algorithms

Given a BST, imagine you want to visit every node once. How would you do that? Well, there are two main approaches, one is Breadth First Search or BFS and the other is Depth First Search or DFS.

Breadth First Search

In BFS, we search a tree horizontally, meaning we capture all the sibling nodes before we move a level deeper in the tree.

Depth First Search

In DFS we search a tree vertically, meaning we work a given path until we reach a leaf node. Then, we move back up to the parent and search the other side until we hit another leaf node.

Within DFS there are three main variants, pre order, in order and post order. These different variants affect how the depth traversal works and each will return a different set of numbers. When to use which depends on the type of data you’re working with.

Pre-Order: This variant is useful if we are looking to ‘export’ our tree structure — maybe by serializing it and storing it in a database. This variant will allow us to re-create the tree if need be.

In-Order: This variant is useful if you need to return the data sorted .

Post-Order: This variant is useful if we are looking to delete a tree node by node. In this variant we start with the leaf nodes and work up to the root node.

Pseudocode for Breadth First Search

We’ll create two arrays, one to store all the values of the nodes we have visited and the other as a queue system to keep track of the nodes we still have left to traverse.

Start by placing the root node in the queue
Loop for as as long as you have a value inside the queue
Dequeue a node. Store it’s value in your collection array. Then, check if that node has a left property, if it does, add it to queue. Then, check if that node has a right property, if it does, add it to the queue.
You’ll repeat this process until your queue is empty. Then, return your array of values.

Implementation Code for Breadth First Search

BFS(){
    let node = this.root
    let queue = [node]
    let visited = []
        
    while (queue.length > 0){
        node = queue.shift();
        visited.push(node.value)        if (node.left) queue.push(node.left)
        if (node.right) queue.push(node.right)    }
    return visited
}

Pseudocode for Depth First Search

It’s a bit easier to solve this problem using recursion. We’ll use helper method recursion where we define a helper function that does the recursion inside our other function, in this manner we can create a persistent data store that won’t be reset every time the recursive function is called.

Create an array to store the visited nodes values
Create a current node, which in the beginning will just be the root node
Inside your helper method (call it traverse), you’ll start by pushing the current node into your collection array.
Then, you’ll check if that node has a left property, if it does, call your traverse function on that left node.
Then, you’ll check if that node has a right property, if it does, call your traverse function on that right node.
Call the traverse function and return the collection array.

*Technically, the above is a solution for Pre Order DFS. For In Order DFS, move step three between steps 4 & 5. For Post Order DFS, move step 3 after step 5.

Implementation Code for DFS (Pre Order, In Order, Post Order)

DFSPreOrder(){
    let visited = []
    let current = this.root    function traverse(node){
        visited.push(node.value)
        if (node.left) traverse(node.left)
        if (node.right) traverse(node.right)
    }    traverse(current)
    return visited
}DFSPostOrder(){
    let visited = []
    let current = this.root    function traverse(node){
        if (node.left) traverse(node.left)
        if (node.right) traverse(node.right)
        visited.push(node.value)
    }    traverse(current)
    return visited
}DFSInOrder(){
    let visited = []
    let current = this.root    function traverse(node){
        if (node.left) traverse(node.left)
        visited.push(node.value)
        if (node.right) traverse(node.right)
    }    traverse(current)
    return visited
}

Breadth First Search vs Depth First Search

Time complexity for each will be the same as we are visiting all the nodes once. Space complexity will differ based off the type of tree we are dealing with. Because we used a recursive solution, the call stack will grow so it is important to be mindful about which searching algorithm you have used and the type tree data you’re working with.

BFS: Since BFS searches a tree horizontally — working through all the sibling nodes before moving a level deeper — we would want to use this method if our tree is very deep.

DFS: Since DFS searches a tree vertically — working through all the child nodes before moving on to siblings — we would want to use this approach if our tree is wide.

In Short: BFS is better for deep trees and DFS is better for wide trees in respect to space complexity for recursive implementation.