Binary Tree And How to Search and Insert With Recursive Functions

When it comes to studying data structures in the sciences of computing, there’s the simple byte, the commonly known array, the fun to implement object, even those linked lists I talked about in the past. Among those I mention, there’s another kind of data structure that will come across in leetcode problems, binary trees.

A binary tree is a data structure in which each parent node can have at most two children. Each one of those items is:

• data item
• address of left child
• address of right child

Picture from Programiz. See references for hyperlinks.

The binary trees are categorized or described as Full, Perfect, Complete, and several Degenerate/Pathological types categories depending on how the nodes and children are connected.

Note: This blog article is about my experience solving leetcode data structure and algorithms issues. If you’d like to create and implement your tree node from scratch, 30 seconds of code have a very informative article to practice.

Now, let’s get to the leetcode reference.

A JavaScript binary TreeNode would look like this.

function TreeNode(val, left, right) {
   this.val = (val === undefined ? 0 : val)
   this.left = (left === undefined ? null : left)
   this.right = (right === undefined ? null : right)
}

That’s the equivalent of creating your classes like this:

class treeNode {
   constructor(val) {
      this.val = val
      this.left = null
      this.right = null
   }
}
class BinarySearchTree {
   constructor() {
      this.root = null
   }
}

We can implement a find or insert using the declared value and roots arguments in a recursive matter. A recursive function will call itself inside its own body. Solving these algorithms using a recursive function helped me understand how they are called and implemented in a binary tree scenario.

Relativity from M.C. Escher is a good visual representation of the patterns and recursion of the following JavaScript functions.

Search

const searchBST = (root, val) => {
    if (!root) return null;
    if(root.val === val) {
        return root;
    } else {
    if(root.val > val) {
        return searchBST(root.left, val);
    } else {
        return searchBST(root.right, val);
      }
    }
};

In this code:

1. We are checking if there’s a root and will return null if there’s no root at all.
2. We’ll return the exact value if that’s the search result.
3. Or else we’ll return the value of the children as well if they’re in the tree.

Although, this might be the best syntax to demonstrate the ability to search values in a binary tree. There’s an even cleaner way to it. First, let’s check if the root node is empty or the same as the value if (!root || root.val === val) return root;. Secondly, we are returning the entire value of the children whether they’re left or right return searchBST(root.left, val) || searchBST(root.right, val);.

The entire function would look like this:

const searchBST = (root, val) => {
   if (!root || root.val === val) return root;
   return searchBST(root.left, val) || searchBST(root.right, val)
};

Insert

const insertIntoBST = (root, val) => {
   if(!root) return new TreeNode(val);
   if (val > root.val) {
      root.right = insertIntoBST(root.right, val);
   } else {
        root.left = insertIntoBST(root.left, val);
   }
   return root;
};

The code for inserting new values in the tree has a similar approach to searching for a given value. This time, we’ll have the root, and the value we have would be the one that we must insert. As you can see in the code above, the function is very similar to the searchBST we coded for searching.

Here’s the function breakdown:

1. If there’s no root, we’re going to create it. In this case, our code in leetcode is new TreeNode(val);.
2. If the root’s value is higher than the value we’re inserting, we’ll insert a new child.
3. Otherwise, we’ll go ahead and insert the given value as the new tree’s root.

As you might be thinking, there is a shorter way to do it. First, we’ll check if there’s no root or if the given value equals the existing root value, if (!root || root.val === val) return new TreeNode(val);. Secondly, we can pretty much code the rest in three lines without curly braces as well as using a ternary operation. However, I like the separate lines way better. Here’s the full function:

const insertIntoBST = (root, val) => {
   if (!root || root.val === val) return new TreeNode(val);
   if(val < root.val) root.left = insertIntoBST(root.left, val);
   else root.right = insertIntoBST(root.right, val);
   return root;
};

Traversal

If we can search and insert values to a binary tree, what about visiting each node? How can we get the information and the flow of the entire tree? Can we do that in different ways? The answer is traversal.

Traversal is any process for visiting all of the objects in a data collection (such as a tree or graph) in some order.

The orders are:

Preorder Traversal

const preorderTraversal = (root) => {
    if (!root) return [];
    
    let queue = [root], result = [];
    
    while (queue.length) {
        const node = queue.pop();
        result.push(node.val);
        if (node.right) queue.push(node.right);
        if (node.left) queue.push(node.left); 
    }
    return result; 
};

Postorder Traversal

const postorderTraversal = (root) => {
    let result = [];
    
    let traverse = (root) => {
        if(root === null) return;
        traverse(root.left);
        traverse(root.right);
        result.push(root.val);
   }
   traverse(root);
   return result;
};

Inorder Traversal

const inorderTraversal = (root) => {
    let result = [];
    
    let traverse = (root) => {
        if(root === null) return;
        traverse(root.left);
        result.push(root.val);
        traverse(root.right);
   }
   traverse(root);
   return result;
};

Trees in coding remind me of picking mangoes from the tree we had in my grandparent’s house. The abstract can mirror the physical more than we imagine, and that’s one of the fun of coding for me.

Perhaps trees of bytes in your computer screen also bring you happy childhood memories, but I also hope you learned something from this. Happy coding!

Summary:

1. Binary tree overview.
2. Recursive functions overview.
3. Search functions.
4. Insert functions.
5. Traversal

References:

1. Progamiz, binary tree
2. 30 seconds of code, Data Structure — JavaScript Binary Tree
3. JavaScript Tutorial, Recursive Function
4. OpenDSA, Binary Tree Traversal