Essential Coding Interview Questions with Javascript (Part III)

(Linked Lists and Trees)

It is very important to get acquainted with various data structures and how to apply them correctly. This article presents the most common interview questions and popular problems with arrays, two-dimensional arrays, queues, stacks, binary search trees, graphs, etc. To be comfortable with this article, you should be familiar with these data structures and have some basic knowledge of Javascript. Examples of these problems I got in Python tutorials, but I wanted to solve them using JavaScript because JS is one of the most popular programming languages and is required for any web developer.

Links to other problems: Part I, Part II

#9 N-th Element of a Linked List

Given a Linked List and a positive number n, write a function that returns the value at the n-th node from end of the Linked List.

For example, if input is below list and n = 1, then output is “E”; n = 4 , output is “B”; n = 7, output is null.

Examples:

Input : 
Linked list: 1->2->3->4->5->6->7,
n = 3
Output : 5
Input : 
Linked list: 11->23->35->41->5->656->17->0,
n = 8
Output : 11

As we can see on visualization of linked list above node with the value “A” is pointing to the node with value “B” and so on. Last node with value “E” in this linked list is pointing to null. To get referral to this list we can by assigning a variable called “head” to the first item in the linked list. Each item or each node in this linked list is an object and the class might look like this:

class Node {
  constructor(value) {
    this.value = value;
    this.child;
  }
};
class LinkedList {
  constructor(){
    this.head;
  }
};

There this problem let’s initialize two variables, left pointer and right pointer, pointing at the first node. Then move the right pointer to the right node n times. After that move both of the pointers to the right, one by one, until the right pointer is pointing at null. When the right pointer will be pointing at null, the left pointer will be pointing at the node we are looking for. If n is bigger than the length of the linked list, right then we should return null.

Solution:

function nthFromLast(head, n) {
  let left = head,
    right = head;
  for (let i = 0; i < n; i++) {
    if (!right) return null;
    right = right.child;
  }
  while (right) {
    right = right.child;
    left = left.child;
  }
  return left;
}

#10 Is This a Binary Search Tree?

Given a binary tree, determine if it is a valid binary search tree (BST).

Examples:

Input : 
     5  = root
    /  \
   2    7
  /\    /\
 0  3  8 10
Output : true
Input : 
     5  = root
    /  \
   2    7
  /\    /\
 0  3  4 10
Output : false
(4 in the right subtree is less than 5 in the root) 

A tree is an abstract model of a hierarchical structure and consists of nodes with a parent-child relationship.

A node in a binary tree has two children at most: one left child and one right child. This definition allows us to write more efficient algorithms to insert, search, and delete nodes to/from a tree. Binary trees are largely used in computer science.

A binary search tree is a binary tree, but it only allows you to store nodes with lesser values on the left-hand side and nodes with greater values on the right-hand side.

class Node { 
  constructor(value){
    this.value = value;
    this.left;
    this.right;
  }
};
class BinarySearchTree{
  constructor(){
    this.root; 
  }
};

A simple solution is for each node, check if the left node of it is smaller than the node and right node of it is greater than the node, but how we can see in the second example it won’t work. We have to create two new variables, which will take track of the current biggest and the current smallest value for current node we are checking. We are starting from the root and our variables will be upperLimit = null, lowerLimit = null, but when we go down for example to the right node side we’ll know that it’s value, new upper limit, should be at least greater than or equal to root’s value, new lower limit. And that when we go to the left node, we know that this value needs to be between the lower limit and upper limit to be a binary search tree. After we check this conditions we have to recursively check if the left subtree and the right subtree is a binary search tree themselves with the new limits that we are going to give them. If they are, return true from our function.

Solution:

function isBST(node, upperLimit = null, lowerLimit = null) {
  if (lowerLimit && node.value < lowerLimit) return false;
  if (upperLimit && node.value > upperLimit) return false;
  let isLeftBST = true,
    isRigthBst = true;
  if (node.left) isLeftBST = isBST(node.left, node.value, lowerLimit);
  if (isLeftBST && node.right)
    isRigthBst = isBST(node.right, upperLimit, node.value);
  return isLeftBST && isRigthBst;
}

#11 Lowest Common Ancestor

Given a binary tree, find the lowest common ancestor (LCA) of two given values in the tree. Assume that there are no duplicates in the tree.

Example:

BT:
      5   = root
     /  \
   11    7
   /\    /\
  0  3  8 10
 / \
1   4
Input : root
n1 = 3
n2 = 4
Output : 11
Input : root
n1 = 11
n2 = 5
Output : 5
Input : root
n1 = 10
n2 = 10
Output : 10

This is a very popular problem and there are many potential solutions to it. Our solution for an interview has to be simple and efficient. As we know from the previous problem, a binary tree has a parent-child structure with up to 2 children.

class Node { 
  constructor(value){
    this.value = value;
    this.left;
    this.right;
  }
};
class BinaryTree{
  constructor(){
    this.root; 
  }
};

To solve this problem, first we have to find nodes that corresponds to given integers in tree before finding their lowest common ancestor. And to find each node will take O(n) in time complexity because our tree is not necessarily sorted and the extra space complexity or auxiliary space will be O(log n), n is the number of nodes in this tree.

We will divide our problem into two parts. First, find a path between the root node, or any other node for that matter, and the integer that we’re looking for. This path will be the stack of nodes from the node with given value to the root node. Once we have these two paths we can examine which elements are common between these two paths, counting from the top. The last item in the common elements in these two paths will be the lowest common ancestor between the given integers.

Now let’s think about how to implement the path to our node. Our function will take two arguments: root and x — one of the given items. We are trying to find the path to x from the node root. We are going to do this recursively. The base case is when we are going to the end node, nonexistent node, we return undefined. And another base case is if the root is equal to an item we are trying to find, we return new Stack with single value — array with the current node. Then we need to ask what the path to the left node and to the right node and move to the subtrees. If x is not under subtree we don’t return anything. Otherwise, if x in the subtree, add the current root to the pass and return that path as the new pass. If x not in the left subtree, not in the right subtree, we return undefined.

Using this function pathToX we can implement our main function lca, which takes three arguments: root node of the tree we are examining, and x1, x2 two integers that we want to find the lowest common ancestor for. We’re going to find the path to x1 and x2 with our pathToX function. If there is no occurrence of x1 or x2 in this tree, we are going to return null. After that we are going to find LCA, initializing variable result. We are going to iterate our path, stored as stacks, from the top one by one, and assigning current equal item to the result until we find different item. Last assigned item to our variable result is our LCA.

Solution:

function pathToX(root, x) {
  if (!root) return;
  if (root.value === x) return [root];
let leftPath = pathToX(root.left, x);
  if (leftPath) {
    leftPath.push(root);
    return leftPath;
  }
  let rightPath = pathToX(root.right, x);
  if (rightPath) {
    rightPath.push(root);  
    return rightPath;
  }
  return;
}
function lca(root, x1, x2) {
  pathTo1 = pathToX(root, x1);
  pathTo2 = pathToX(root, x2);
  if (!pathTo1 || !pathTo2) return null;
  let result;
  while (pathTo1.length > 0 && pathTo2.length > 0) {
    pop1 = pathTo1.pop();
    pop2 = pathTo2.pop();
    if (pop1 === pop2) result = pop1;
    else break;
  }
  return result;
}