Binary Tree Interview Questions

10 min readAug 3, 2019

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. For more information please refer to https://en.wikipedia.org/wiki/Binary_tree

I’ll be covering the most common interview questions related to this topic asked in companies like Google, Microsoft, Amazon…:

size of a tree
height of a tree
path to leaf with a sum
level of node
the diameter of a tree
postorder traversal (iterative)
preorder traversal (iterative)
inorder traversal (iterative)
depth-first search (dfs)
breadth-first search (bfs)
serialize & deserialize a tree
find a node
find out how many tree(s) can be constructed with n node(s)
binary tree to LinkedList using bfs
binary tree to LinkedList using inorder traversal
check if two trees are isomorphic
print a tree in a spiral order
print nodes having k leaves
find the lowest common ancestor
vertical order traversal
print diagonal sum of a tree
level order traversal
left, right, top & bottom view of a tree
print all the path from root to leaf
number of leaf nodes in a tree
check if a tree is a sum tree

Creating a node class

class Node{
  constructor(val=null){
    this.val = val
    this.left = null
    this.right = null
  }

  setRight(newNode){
    this.right = newNode
  }

  setLeft(newNode){
    this.left = newNode
  }
}

Creating a Binary Tree class

class BinaryTree{
  constructor(node){
    this.root = node
  }

  setleft(node){
    let cur = this.root
    while(cur.left !== null){
      cur = cur.left
    }
    cur.left = node
  }

  setRight(node){
    let cur = this.root
    while (cur.right !== null){
      cur = cur.right
    }
    cur.right = node
  }
}

For calculating the size of a tree do a summation of left, root & right node recursively.

size(root){
  if(root === null){
    return 0
  }
  //left+root+right
  return this.size(root.left)+1+this.size(root.right)
}

The maximum depth or height of a binary tree is the number of nodes along the longest path from the root node down to the farthest leaf node. Recursively call the function for the left node and right node and return the max of the left height or right height plus 1.

height(root){
  if(root === null){
    return 0
  }
  const lHeight = this.height(root.left)
  const rHeight = this.height(root.right)

  return Math.max(lHeight, rHeight)+1
}

Now let's see how to find out the paths from the root to leaf with a given sum.

pathToLeafWithSum(root, sum, stack){
  if(root === null){
    return false
  }
  if(root.left === null && root.right===null){
    if(root.val === target){
      stack.push(root.val)
      return true
    }else{
      return false
    }
  }
  if(this.pathToLeafWithSum(root.left, sum-root.val, stack)){
    stack.push(root.val)
    return true
  }
  if(this.pathToLeafWithSum(root.right, sum-root.val, stack)){
    stack.push(root.val)
    return true
  }
}

The level of a node is defined by 1 + the number of connections between the node and the root. Now, to find out a level of a node from the root, call the level function recursively for the left and right nodes until it matches the target node.

level(root,target,l=1){
  let level = null
  if(root === null){
    return 0
  }
  if(root.val === target){
    return l
  }

  level = this.level(root.left,target, l+1)
  if(level!==0) return level
  level = this.level(root.right,target, l+1)

  return level
}

The diameter of a binary tree is the number of nodes on the longest path in a binary tree is the diameter. If the longest path passes through the root then the diameter can be calculated from the summation of the height of the left subtree, right subtree, and the root node. Otherwise, recursively call the diameter function for left and right subtree.

diameter(root){
  if(root === null){
    return 0
  }
  let lHeight = BT.height(root.left)
  let rHeight = BT.height(root.right)

  let lDiameter = this.diameter(root.left)
  let rDiameter = this.diameter(root.right)


  return Math.max(...[lHeight+rHeight+1, lDiameter, rDiameter])
}

Tree traversal with postorder, preorder & inorder

It's very easy to do the above three traversals recursively but I wanted to show you how to do it iteratively. In the interview, the interviewer wanted to see if the interviewee has really understood the concept of tree traversal. Because most of the tree problem can be solved with this traversal algorithm. Let's dive into the code.

       10
    9     11
   8     4
  7
5  17Postorder: [5, 17,  7,  8, 9,  4, 11, 10]postOrderTraversal(){
  let stack = []
  let output = []
  let cur = this.root

  stack.push(cur)

  while(stack.length){
    const top = stack.pop()
    output.unshift(top.val)
    if(top.left){
      stack.push(top.left)
    }
    if(top.right){
      stack.push(top.right)
    }
  }
  return output
}Preorder: [10,  9,  8, 7, 5, 17, 11, 4]predorderTraversal(){
  let cur = this.root
  let stack = []
  let output = []

  while(true){
    while(cur){
      stack.push(cur)
      output.push(cur.val)
      cur = cur.left
    }
    if(stack.length===0) break
    const lastNode = stack.pop()
    cur = lastNode.right
  }
  return output
}Inorder: [5,  7, 17,  8, 9, 10,  4, 11]inorderTraversal(){
  let cur = this.root
  let stack = []
  let output = []

  while(true){
    while(cur){
      stack.push(cur)
      cur = cur.left
    }
    if(stack.length === 0) break

    const lastNode = stack.pop()
    output.push(lastNode.val)
    cur = lastNode.right
  }
  return output
}

Depth-first search (DFS) or Breadth-first search (BFS) is an algorithm for traversing or searching tree data structures. In DFS, start from the root and traverse the left subtree until it's null and then go to the right subtree. Whereas in BFS, traversing is done in level order.

dfs(root, stack = []){
  if(root === null) return null

  stack.push(root.val)

  if(root.left){
    this.dfs(root.left, stack)
  }
  if(root.right){
    this.dfs(root.right, stack)
  }
  return stack
}

bfs(){
  let cur = this.root
  let queue = []
  let output = []

  queue.push(cur)

  while(queue.length){
    const node = queue.shift()
    output.push(node.val)

    if(node.left){
      queue.push(node.left)
    }
    if(node.right){
      queue.push(node.right)
    }
  }
  return output
}

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Let's dive into the solution:

serialize(){
  const preOrderNodes = this.predorderTraversal()
  return preOrderNodes.join(',')
}

deserialize(){
  const preOrderNodes = this.predorderTraversal()
  const inOrderNodes = this.inorderTraversal()
  return this.createTree(preOrderNodes, inOrderNodes)
}

createTree(preOrderNodes, inOrderNodes){
  if(preOrderNodes.length === 0 || inOrderNodes.length===0) return null

  const rootVal = preOrderNodes.shift()
  const index = inOrderNodes.indexOf(rootVal)
  const left =  inOrderNodes.slice(0,index)
  const right = inOrderNodes.slice(index+1)
  const root = new Node(rootVal)
  root.left = this.createTree(preOrderNodes, left)
  root.right = this.createTree(preOrderNodes, right)

  return root
}

To serialize a tree we have used the preorder traversal method of a binary tree and return it in the form of a string, pretty simple. But to deserialize it we need both preorder and inorder traversal nodes. Preorder nodes will give us the root node and search that node in inorder nodes to create the left and right subtree.

Search an element in a binary tree

Searching an element in a binary tree is pretty simple, any tree traversal method could be used. But in this solution, I’ll be using the recursive preorder traversal. Check for the current node if it’s not the element then go to left and then right recursively.

find(root, element){
  let found = false
  if(root.val === element) return true

  if(root.left){
    found = this.find(root.left, element)
    if(found) return true
  }
  if(root.right){
    found = this.find(root.right, element)
    if(found) return true
  }
  return false
}

Find out how many BST can be constructed with n distinct node(s)

For, n = 0 i.e. no nodes are given then the number of BST that can be constructed is 1 (null node).

For n = 1 i.e. with one node, let’s say as per the diagram the node is 5, then the number of BST that can be constructed is 1.

For n = 2 i.e. with 2 nodes, let’s say as per the diagram the nodes are 5,6 then the number of BST that can be constructed are {5,6} and {6,5}. 5 as the root node and 6 as the root node. Keeping in mind in BST rule nodes greater than the root goes on the right and smaller than the root goes on the left.

For n = 3 i.e. with 3nodes, let’s say as per the diagram the nodes are 5,6,7 then the number of BST that can be constructed are {5,6,7},{5,7,6},{6,5,7},{7,5,6} and {7,6,5}.

static countTrees(n){
  const dp = Array(n).fill(0)
  //base condition
  dp[0] = dp[1] = 1

  for(let i =2; i<=n; i++){
    dp[i] = 0
    for(let j =0;j<i; j++){
      dp[i] += dp[j]*dp[i-j-1]
    }
  }
  return dp[n]
}

As per the base condition, it’s already known that with n as 0 and n as 1 number of BST that can be constructed is 1. So, the concept is to take each node as root and placing the other nodes either on the left or right (if it’s smaller or greater). Multiply the number of nodes found from each root node and then summate all the values of each node.

Binary Tree to Linked List using BFS

A linked list is a sequence of data structures, which are connected together via links. For more info https://en.wikipedia.org/wiki/Linked_list.

Creating a Linked List class

class LinkedList {
  constructor(val){
    this.val = val
    this.left = null
    this.right = null
  }
}

If you have seen my BFS traversal code above we’ll be using exactly the same piece of code and just add a few more lines to create a linked list.

binaryTreeToLinkedList(){
  let cur = this.root
  let queue = []
  let prev = null
  let head = null

  queue.push(cur)

  while(queue.length){
    const node = queue.shift()
    const ll = new LinkedList(node.val)
    if(head === null){
      head = ll
    }else{
      ll.left = prev
      prev.right = ll
    }
    prev=ll

    if(node.left){
      queue.push(node.left)
    }
    if(node.right){
      queue.push(node.right)
    }
  }
  return head
}

Highlighted snippets are the newly added lines on the BFS traversal code. Create a linked list node from the current node and if the head is null (initially) add that linked list node to the head and store that node for next iteration where it’s needed to point the current nodes left to the previous node and previous node right to the current node.

Now let's try creating a Linked List from inorder traversal.

inorderBasedbinaryTreeToLinkedList(){
  let head = null
  let prev = null
  let stack = []
  let cur = this.root

  while(true){
    while(cur){
      stack.push(cur)
      cur = cur.left
    }
    if(stack.length === 0) break
    const lastNode = stack.pop()
    const ll = new LinkedList(lastNode.val)
    if(head === null){
      head = ll
    }else{
      prev.right = ll
      ll.left = prev
    }
    prev = ll

    cur = lastNode.right
  }
  return head
}

Isomorphic Trees

Two trees are called isomorphic if one of them can be obtained from others by a series of flips, i.e. by swapping left and right children of a number of nodes.

To find if two trees are isomorphic, recursively compare the nodes of one tree with another. Here’s the simple solution:

isIsomorphic(node1, node2){
  if(node1 === null && node2 === null){
    return true
  }
  if(node1 !== null || node2 !== null){
    return false
  }
  if(node1.val !== node2.val){
    return false
  }

  if((isIsomorphic(node1.left, node2.left) && isIsomorphic(node1.right, node2.right)
    || isIsomorphic(node1.left, node2.right) && isIsomorphic(node1.right, node2.left))){
    return true
  }
}

Printing a tree in spiral order

The idea is to use two stacks. We can use one stack for printing from left to right and another stack for printing from right to left. In every iteration, we have nodes of one level in one of the stacks. We print the nodes and push nodes of the next level in another stack.

spiralOrderBinaryTree(){
  const cur = this.root
  let stack1 = []
  let stack2 = []
  let output = []

  stack1.push(cur)
  while(true){
    while(stack1.length){
      const node = stack1.pop()
      output.push(node.val)
      if(node.left){
        stack2.push(node.left)
      }
      if(node.right){
        stack2.push(node.right)
      }
    }
    while(stack2.length){
      const node = stack2.pop()
      output.push(node.val)
      if(node.right){
        stack1.push(node.right)
      }
      if(node.left){
        stack1.push(node.left)
      }
    }

    if(stack1.length === 0 && stack2.length === 0) break
  }

  return output
}

Nodes in a binary tree having K leaves

We’ll use postorder traversal to find the nodes. Sum of leaves in the left subtree and in right subtree must be equal to K.

printNodesHavingKLeaves(root, num){
  if(root === null) return 0
  if(root.left === null && root.right === null){
    return 1
  }
  const l = this.printNodesHavingKLeaves(root.left,num)
  const r = this.printNodesHavingKLeaves(root.right,num)
  const t = l+r
  if(t === num){
    console.log(root)
  }
}

Lowest Common Ancestor in a Binary Tree

We’ll be traversing the tree starting from the root. If any of the given nodes matches with root, then the root is LCA. If the root doesn’t match with any of the nodes, we recur for left and right subtree.

lowestCommonAncestor(root, node1, node2){
  if(root === null) return null
  if(root.val === node1 || root.val === node2) return root
  const l = this.lowestCommonAncestor(root.left, node1, node2)
  const r = this.lowestCommonAncestor(root.right, node1, node2)

  if(l && r){
    console.log(`lowestCommonAncestor`)
    return root
  }else{
    return l ? l :r
  }
}

Vertical Order traversal

An efficient solution based on the hash map is discussed here. We need to check the Horizontal Distances from the root for all nodes. If two nodes have the same Horizontal Distance (hd), then they are on the same vertical line. The idea of hd is simple. hd for root is 0, a right edge is considered as +1 horizontal distance and a left edge is considered as -1 horizontal distance. While traversing the tree, we can recursively calculate hds. We initially pass the horizontal distance as 0 for root. For left subtree, we pass the Horizontal Distance as Horizontal distance of root minus 1. For right subtree, we pass the Horizontal Distance as Horizontal Distance of root plus 1. For every HD value, we maintain a list of nodes in a hash map. Whenever we see a node in traversal, we go to the hash map entry and add the node to the hash map using HD as a key in a map.

// initial hd value assigned to a node is 0
class Node{
  constructor(val=null){
    this.val = val
    this.left = null
    this.right = null
    this.hd = 0
  }
}
verticalOrder(){
  let queue = []
  let map = {}
  let cur = this.root

  queue.push(cur)

  map[cur.hd] = [cur.val]

  while(queue.length){
    const node = queue.shift()

    if(node.left){

      const lhd = node.hd-1
      node.left.hd = lhd
      queue.push(node.left)
      if(!map[lhd]){
        map[lhd] = [node.left.val]
      }else{
        map[lhd].push(node.left.val)
      }
    }

    if(node.right){
      const lhd = node.hd+1
      node.right.hd = lhd
      queue.push(node.right)
      if(!map[lhd]){
        map[lhd] = [node.right.val]
      }else{
        map[lhd].push(node.right.val)
      }
    }

  }
  return map
}

For the remaining solution keep an eye on my next article on Binary Trees.

Binary Tree Interview Questions

Written by Anik Dutta