Getting Started with Trees: Binary and Binary Search Trees

Welcome back, readers!

It’s great to have you back for the third sequel of my blog on trees. I hope you’re ready for another exciting chapter filled with informative and engaging content.

Here, part-1 for the concepts of height and depth and part-2 for traversal methods, if you want to check them out.

In this blog, we will dive into the world of binary trees and binary search trees.

Related LeetCode problems will be solved for a better understanding of the concept.

Let’s begin!

What are a Binary Tree and a Binary Search Tree?

A binary tree is a type of tree data structure where each node can have at most two children, which are referred to as the left child and the right child.

A binary search tree is a data structure in that each node in the tree has at most two children and the value of the left child is less than its parent node, and the value of the right child is greater than its parent node.

Binary Search Tree

Its structure allows us to perform efficient searching, insertion, and deletion of elements.

Time and Space Complexity of a Binary Search Tree

The Average Case

In the average case, the tree is balanced, which means that the number of nodes in the left and right subtrees of each node is roughly equal.

While searching for a key in the tree, the search algorithm starts at the root of the tree and compares the key to the key at the root. If the key matches, the search is successful. Otherwise, if the key is smaller than the root key, the search continues in the left subtree, and if the key is larger than the root key, the search continues in the right subtree.

This property ensures that the search algorithm has to traverse approximately half of the nodes in each level of the tree before finding the key.

Therefore, the number of nodes visited during a search (it is also the same as inserting and deleting elements) is proportional to the height of the tree, which is logarithmic in the number of nodes, i.e., O(log n).

The Worst Case

The worst-case scenario for the efficiency of a binary search tree is when the tree is unbalanced, the height of the tree could be as high as n, where n is the number of elements in the tree. The search algorithm has to visit all nodes in the tree.

In this case, the time complexity for searching, inserting, or deleting elements in the binary search tree would be O(n), which is equivalent to a linear search.

Problems from LeetCode

I have selected some problems that are related to binary search trees. Let’s first understand the questions and implement our approaches step by step.

700. Search in a Binary Search Tree

The question: Find the node in the BST that the node’s value equals val and return the subtree rooted with that node. If such a node does not exist, return null.

The approach: We can use recursion to look for the value inside the binary tree. We can have two base cases.

• If the searched value is not inside the tree, return null.
• If we have found the value, return the current root.

Since this is a binary tree, we can compare the values of the left (less than the root’s value) and right ( higher than the root’s value) and the value we are looking for. If the value “val” is more than the root’s value, we should look for the right sub-tree. And the logic works both ways.

Let’s see how we can implement this approach:

var searchBST = function(root, val) {
    if(!root) return null
    if(root.val === val) return root

    while(root){
      if(root.val > val) {
        // should be in the left of the tree
      return searchBST(root.left,val)
      } else {
      return searchBST(root.right,val)
      }
    }
};

701. Insert into a Binary Search Tree

The problem: You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

The approach: First, we must decide where this value can stand in this binary search tree.

If the value is less than the current node’s value, you continue the search in the left subtree. If the new value is greater than the current node’s value, you continue the search in the right subtree. You repeat this process until you reach a null node, which indicates the location where the new value should be inserted as a new leaf node.

var insertIntoBST = function(root, val) {
    if (!root) return new TreeNode(val);

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

If the new value is less than the current node’s value, the function updates the current node's left child with the result of the recursive call. If the new value is greater than the current node's value, the function updates the right child of the current node with the result of the recursive call. Finally, it returns the root node of the binary search tree.

108. Convert Sorted Array to Binary Search Tree

The question: Given an integer array where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Input: nums = [-10,-3,0,5,9]

Output: [0,-3,9,-10,null,5]  

or it can be like this

Output: [0,-10,5,null,-3,null,9]

The approach: The basic idea is to find the middle element of the current subarray and make it the root node of the binary search tree.

Then, we will recursively create the left and right subtrees by converting the left and right subarrays into binary search trees.

var sortedArrayToBST = function(nums) {
    return buildTree(nums, 0, nums.length - 1);
};

var buildTree = function(nums, start, end) {
    if (start > end) return null;
    
    let mid = Math.floor((start + end) / 2);
    let root = new TreeNode(nums[mid]);
    
    root.left = buildTree(nums, start, mid - 1);
    root.right = buildTree(nums, mid + 1, end);
    
    return root;
};

The left subtree is built using the indices start and mid - 1, and the right subtree is built using the indices mid + 1 and end.

236. Lowest Common Ancestor of a Binary Tree

The problem: Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

The approach: To find the lowest common ancestor (LCA) of two given nodes in a binary tree, one way is to start at the root node and compare its value to the values of the two given nodes.

If the root node’s value is between the two given nodes’ values, it is the LCA. If the root node’s value is larger than both given node’s values, then move to the left subtree and repeat the process. If the root node’s value is smaller than both given node’s values, then move to the right subtree and repeat the process. This process is done repeatedly until the LCA is found.

var lowestCommonAncestor = function(root, p, q) {
    if (!root || root === p || root === q) {
        return root;
    }
    
    const left = lowestCommonAncestor(root.left, p, q);
    const right = lowestCommonAncestor(root.right, p, q);
    
    if (left && right) {
        return root;
    } else {
        return left ? left : right;
    }
};

Let’s go step by step:

• If the root is null, or if the root is either p or q, we return the root.
• Recursively searching the left and right subtrees for the LCA of p and q.
• If both left and right are not null, then p and q are in different subtrees, and the root is the LCA.
• Otherwise, it returns the non-null value, which is the LCA.

100. Same Tree

The problem: Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Input: p = [1,2], q = [1,null,2]
Output: false

The approach:

var isSameTree = function(p, q) {
    if(!p && !q) return true
    if((p && !q) || (q && !p)) return false

    if(p.val === q.val) {
         const left  = isSameTree(p.left, q.left)
         const right  = isSameTree(p.right, q.right)
         return left && right
    }
  
  return false
};

Conclusion

Binary trees and binary search trees allow for efficient searching, insertion, and deletion of elements. Binary search trees, in particular, provide logarithmic time complexity for these operations in the average case. However, their worst-case time complexity can be linear if the tree is not balanced. It is important to keep the tree balanced for optimal performance.

Overall, understanding and implementing binary trees and binary search trees can be very useful in solving a variety of programming problems, especially those that involve sorting or searching data.