BST insertion

See the Pen BST insertion by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Find corresponding Node of a second tree, given the node of a tree

See the Pen Corresponding DOM Node in 2nd DOM Tree by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Apple Phone Interview Question

Someone recently asked me what's the point of such questions where you get something from one tree and find something based on it in a second tree. Such kind of algorithms are useful for libraries like React. React is a UI development library that has optimized rendering for the browser. 

The browser renders HTML in the form of DOM (Document Object Model) tree. Any update to the DOM is cascaded down this tree (involves tree processing complexity) and then the browser re-paints the changes. And these operations on the DOM tree are all pretty expensive.

What React does is to create a copy of the HTML DOM - this copy DOM tree is called the Shadow DOM. Any update you make to the DOM is first made on the Shadow DOM and then all the updates are batched together and sent to the actual HTML DOM. As a result, the number of times the browser re-paints the DOM is highly reduced. Thus using React provides you with faster/optimized renderings. 

In order for React to do what it does with it's own shadow tree and the HTML DOM Tree, it needs to do things with one tree and transfer it to the other tree. 

Maximum Depth of Binary Tree

See the Pen Maximum Depth of Binary Tree by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Most Frequent Subtree Sum

See the Pen Most Frequent Subtree Sum by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Tree Path Sum

See the Pen Tree Path Sum by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS Preorder (Stacks)

See the Pen Binary Tree - DFS Preorder (Stacks) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS PostOrder (Recursion)

See the Pen DFS - Binary Tree PostOrder (Recursion) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS PreOrder (Recursive)

See the Pen Binary Tree DFS Pre-order traversal by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Binary Tree - DFS Inorder Traversal (Recursion)

See the Pen DFS - Binary Tree Inorder (Recursion) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Tree BFS in JS (Queue/Array)

Tree properties

1. The maximum number of nodes at level ‘l’ of a binary tree is 2^l
2. The Maximum number of nodes in a binary tree of height ‘h’ is 2^h – 1, Height of a tree with a single node is considered as 1.

BFS Complexity
Time Complexity - O(n)
Space Complexity - O(n)

Notes: BFS slower than DFS

From geeksforgeeks: 

Extra space required for Level order traversal is likely to be more when tree is more balanced and extra space for Depth First Traversal is likely to be more when tree is less balanced.

How to Pick One?

1. Extra Space can be one factor (Explained above)
2. Depth First Traversals are typically recursive and recursive code requires function call overheads.
3. The most important points is, BFS starts visiting nodes from root while DFS starts visiting nodes from leaves. So if our problem is to search something that is more likely to closer to root, we would prefer BFS. And if the target node is close to a leaf, we would prefer DFS.

Exercise:
Which traversal should be used to print leaves of Binary Tree and why? DFS
Which traversal should be used to print nodes at k’th level where k is much less than total number of levels? BFS

See the Pen Tree BFS in JS (Recursive & Non-recursive Queue versions) by Dhiviya Dhanasekar (@dhiviyadhanasekar) on CodePen.

Subtree Sum

Problem

Find subtrees with nodes that add to a given sum

Example Input:

Sum = 5
Tree is:

            1
    /   \
           2     3
         / \   / \
      2  -1 0   8
      /\   /\           /\   /\
   0  3 -5 4     6 -9 -6 1

Output: 

2 

0 3 

null null null null 

--------------------

2 

2 -1 

0 3 -5 4 

null null null null null null null null 

--------------------

Solution

package Tree;

import java.util.ArrayList;

public class SubtreeSum {

	private ArrayList sumPaths;

	private Integer traverse(Tree t, int sum){
		if(t == null) return 0;

		Integer leftSum = traverse(t.left, sum);
		Integer rightSum = traverse(t.right, sum);
//		if(leftSum == null || rightSum == null) return null;
		Integer curSum = leftSum + rightSum + t.val;

//		if(curSum > sum) return null;
		if(curSum == sum) { sumPaths.add(t);}
		return curSum;
	}
	
	public void printSubTreeWithSum(Tree t, int sum){
		sumPaths = new ArrayList();
		traverse(t, sum);
		
		for(int i = 0; i < sumPaths.size(); i++){
			TreeOperations.printTree(sumPaths.get(i));
			System.out.println("--------------------");
		}
	}
	
	public static void main(String[] args) {
		SubtreeSum ob = new SubtreeSum();
		Tree t = TreeTestData.getSampleTree3();
		ob.printSubTreeWithSum(t, 5);
	}
}

Tree - Sum Paths

Problem

Given a binary tree, not necessarily a BST return all paths with sum x:
Example for sum =5 and tree given below:

         1
        /   \
           2     3
         / \          / \
      2  -1      0   8
      /\   /\       /\     /\
   0  3 -5 4   6 -9 -6 1

Output is: [[1,2,2],[2,3],[1,2,2,0],[2,-1,4],[3,8,-6]]

Solution

public class Tree{
	int val;
	Tree left;
	Tree right;
} 

package Tree;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class TreeSumPath {

	Set< ArrayList<Integer> > sumPaths2;
	
	void doTraversal(Tree t, int remain, int oSum, ArrayList temp){
		temp.add(t.val);
		if(remain == 0) sumPaths2.add(temp);
		traverse2(t.left, remain, temp, oSum);
		traverse2(t.right, remain, temp, oSum);
	}
	
	void traverse2(Tree t, int sum, ArrayList curNodes, int oSum){
		if(t==null) return;
		ArrayList temp = new ArrayList(curNodes);
		doTraversal(t, sum - t.val, oSum, temp);
		
		temp = new ArrayList();
		doTraversal(t, oSum-t.val, oSum, temp);
	}

	Set< ArrayList<Integer> > getSumPaths(Tree t, int sum){
		sumPaths2 = new HashSet< ArrayList>();
		traverse2(t, sum, new ArrayList(), sum);
		System.out.println(sumPaths2);
		return sumPaths2;
	}
	
	public static void main(String[] args) {
		Tree t = TreeTestData.getSampleTree3();
		TreeSumPath ob = new TreeSumPath();
		ob.getSumPaths(t, 5);
	}
}

Morris Tree Traversal (Pre & In order)

package Tree;

public class MorrisTraversal {
 //nlogn time complexity
 //but 1 space complexity => saves memory
 
 public void morrisPreorder(Tree t)
 {
  while(t!= null) 
  {
   if(t.left == null)
   {
    System.out.print(t.val + " ");
    t = t.right;
   }
   else
   {
    Tree pre =  t.left;
    while(pre.right != null && pre.right != t) 
     pre = pre.right;
    
    if(pre.right == null)
    {
     System.out.print(t.val + " ");
     pre.right = t;
     t = t.left;
    }
    else
    {
     pre.right  = null;
     t = t.right;
    }
   }
  }
 }
 
 public void morrisInorder(Tree t){
  while(t != null) 
  {
   if(t.left == null) 
   {
    System.out.print(t.val + " ");
    t = t.right;
   }
   else 
   {
    Tree temp = t.left;
    while(temp.right != null && temp.right != t)
    {
     temp = temp.right;
    }
    
    if(temp.right == null)
    {
     temp.right = t;
     t = t.left;
    }
    else 
    {
     temp.right = null;
     System.out.print(t.val + " ");
     t = t.right;
    }
   }
  }
 }

 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int[] pre = {10,5,1,2,7,50,100};
  BSTFromPre ob = new BSTFromPre();
  Tree t = ob.reContructTree(pre);
  TreeOperations.printTree(t);
  System.out.println("-------------------------");
  
  MorrisTraversal morris =  new MorrisTraversal();
//  morris.morrisInorder(t);
  morris.morrisPreorder(t);
  
 }
}

BST Biggest Subtree within a range

Problem

Given a binary search tree t and a range (a,b), find number of nodes in the largest subtree or tree, whose nodes are in the range of (a,b). a, b are exclusive for the range.

Solution

public class BSTRange {
 
 private int max = 0;
 private boolean valid(int val, int a, int b){
  if(val > a && val < b) return true;
  return false;
 }

 private Integer postOrder(Tree t, int a, int b){
  if(t== null) return 0;

  Integer leftCnt = postOrder(t.left, a, b);
  Integer rightCnt = postOrder(t.right, a, b);

  if(leftCnt == null || rightCnt == null) return null;
  if(!valid(t.node, a, b)) return null;

  int cnt = 1 + leftCnt + rightCnt;
  if(max < cnt) max = cnt;
  return cnt; 
 }

 public int getMaxNodesInRange(Tree t, int a, int b){
  max =0;
  postOrder(t, a, b);
  return max;
 }

 public static void main(String[] args) {

  int[] preOrderData = {10,5,1,2,7,50,100};
  BSTFromPre ob = new BSTFromPre();
  Tree t = ob.reContructTree(preOrderData);
  TreeOperations.printTree(t);

  BSTRange ob1 = new BSTRange();
  System.out.println(ob1.getMaxNodesInRange(t, 0, 101));
 }
}

Reservoir Sampling - Tree

Problem

Get n random nodes from a binary tree, such that each node will be returned with equal probability.

Solution

import java.util.ArrayList;
import java.util.Random;

public class Tree {
 public int node;
 public Tree left;
 public Tree right;
}
public class NodesAtRandom {
 
 int index = 0;
 ArrayList getRandomNodes(Tree t, int n){
  ArrayList ret = new ArrayList();
  index =0;
  preOrder(ret, t, n);
  return ret;
 }
 
 private void preOrder(ArrayList ret, Tree t, int n) {
  if(t==null) return;
  index++;
  if(ret.size() < n) ret.add(t.node);
  else {
   Random r = new Random();
   int rVal = r.nextInt(index);
   if(rVal < n) ret.set(rVal, t.node);
  }
  preOrder(ret, t.left, n);
  preOrder(ret, t.right, n);
 }

 public static void main(String[] args){
  Tree t = TreeTestData.getSampleTree1();
  TreeOperations.printTree(t);
  NodesAtRandom ob = new NodesAtRandom();
  ArrayList output = ob.getRandomNodes(t, 2);
  System.out.println(output);
 }
}

Construct Tree from PreOrder & InOrder

Problem 

Construct a tree from pre-order and in-order traversal arrays.
What I learnt here? - Arrays.copyOfRange(int[], int start, int end) copies from start (included) till end-1 (i.e. exclusive of end)

Solution

import java.util.Arrays;
public class TreeProblem2 {
 class Tree {
  int node;
  Tree left;
  Tree right;
 }
 
 int preIndex = 0;
 Tree construct(int[] pre, int[] in) {
  if(preIndex >= pre.length  || in.length==0) return null;

  Tree t= new Tree();
  t.node = pre[preIndex++]; //first element in preorder is the root

  //Get pos of root in the inorder. 
  //Elements left of that will be the left tree
  //Elements to the right of that will be the right tree
  int i =0;
  for(;i< in.length; i++){
   if(in[i] == t.node) break;
  }

  int[] leftIn = Arrays.copyOfRange(in, 0, i);
  int[] rightIn = Arrays.copyOfRange(in, i+1, in.length);

  t.left = construct(pre, leftIn);
  t.right = construct(pre, rightIn);
  return t;
 }

 public static void main(String[] args) {
  int[] pre = {10,5,80,9,2,6};
  int[] in = {80,5,9,10,6,2};
  TreeProblem2 ob = new TreeProblem2();
  Tree t = ob.construct(pre, in);
  TreeOperations.printTree(t);
 }
}

Construct BST from PreOrder traversal array

Problem

Given an preorder traversal array as input, reconstruct a binary search tree.

Solution

public class Tree {
 public int node;
 public Tree left;
 public Tree right; 
}

public class TreeProblem1 extends Tree{
 int index = 0;
 Tree construct(int[] pre, int min, int max)
 {
  if(index>=pre.length) return null;
  if(pre[index]>max || pre[index] < min) return null;
  Tree t = new Tree();
  t.node = pre[index++];
  t.left = construct(pre,min, t.node);
  t.right = construct(pre, t.node, max);
  return t;
 }
 
 Tree reContructTree(int[] preorder)
 {
  index = 0;
  return construct(preorder, Integer.MIN_VALUE, Integer.MAX_VALUE);
 }
 
 public static void main(String[] args) {
  
  int[] pre = {10,5,1,2,7,50,100};
  TreeProblem1 ob = new TreeProblem1();
  Tree t = ob.reContructTree(pre);
  TreeOperations.printTree(t);
 }

}

Tree Depth First Searches

public class Tree {
 public int nodeValue;
 public Tree leftNode;
 public Tree rightNode; 
}

public class TreeOperations {

 public void preorderSearch(Tree t)
 {
  if(t == null) return;
  System.out.print(t.nodeValue + " ");
  preorderSearch(t.leftNode);
  preorderSearch(t.rightNode);
 }
 
 public void inorderSearch(Tree t)
 {
  if(t == null) return;
  inorderSearch(t.leftNode);
  System.out.print(t.nodeValue + " ");
  inorderSearch(t.rightNode);
 }
 
 public void postorderSearch(Tree t)
 {
  if(t==null) return;
  postorderSearch(t.leftNode);
  postorderSearch(t.rightNode);
  System.out.print(t.nodeValue + " " );
 }

 public static void main(String[] args) {

  Tree t = TreeTestData.getSampleTree1();
  TreeOperations  treeOps = new TreeOperations();
  treeOps.preorderSearch(t);
  treeOps.inorderSearch(t);
  treeOps.postorderSearch(t);
 }

}

Note: For the TreeTestData Class look at post Tree part 1 step 2.

Display Tree (Breadth First Search Output)

Step1: Write Tree class 

public class Tree {
 public int nodeValue;
 public Tree leftNode;
 public Tree rightNode;
}

Note: You can write get set functions, instead of declaring the tree members as public

Step 2: Write a sample test input & functions for it

public class TreeTestData {

 public static Tree createNode(int nodeVal, int left, Tree right)
 {
  Tree t = new Tree();
  t.nodeValue = nodeVal;
  t.leftNode = createNode(left, null, null);
  t.rightNode = right;
  return t;
 }
 
 public static Tree createNode(int nodeVal, int left, int right)
 {
  Tree t = new Tree();
  t.nodeValue = nodeVal;
  t.leftNode = createNode(left, null, null);
  t.rightNode = createNode(right, null, null);
  return t;
 }
 public static Tree createNode(int nodeVal, Tree left, Tree right)
 {
  Tree t = new Tree();
  t.nodeValue = nodeVal;
  t.leftNode = left;
  t.rightNode = right;
  return t;
 }
 
 public static Tree getSampleTree1()
 {
  Tree right = createNode(3, 2, 4);
  Tree currentLeftTree = createNode(1, 0, right);
  right = createNode(8,7,null);
  Tree currentRightTree = createNode(6, null, right);
  Tree t = createNode(5, currentLeftTree, currentRightTree);
  return t;
 }
}

Step 3: Construct an array of arrays using depth first search pre-order to store the nodes at each level. Go through the array using breadth first search and print the tree. If a node doesn't have a particular child, -1 is printed in this code.

import java.util.ArrayList;

public class TreeOperations {

 public void printNodeRecursively(Tree t, int level, 
              ArrayList<ArrayList<Integer>> levelNodes)
 {
  if(levelNodes.size() == level)
  {
   levelNodes.add(new ArrayList());
  }
  ArrayList nodes = levelNodes.get(level);
  if(t == null)
  {
   nodes.add(-1);
   return;
  }
  nodes.add(t.nodeValue);
  printNodeRecursively(t.leftNode, level+1, levelNodes);
  printNodeRecursively(t.rightNode, level+1, levelNodes);
 }

 public void printTree(Tree t)
 {
  final ArrayList<ArrayList<Integer>> levelNodes = new ArrayList<ArrayList<Integer>>();

  printNodeRecursively(t, 0, levelNodes);

  for(int level=0; level < levelNodes.size(); level++)
  {
   for(int nodeIndex = 0; nodeIndex < levelNodes.get(level).size(); nodeIndex++)
   {
    System.out.print(levelNodes.get(level).get(nodeIndex));
    System.out.print(" ");
   }
   System.out.println();
  }
 }

 public static void main(String[] args) {
  Tree t = TreeTestData.getSampleTree1();
  TreeOperations  treeOps = new TreeOperations();
  treeOps.printTree(t);
 }
}