## Optimal Binary Search Trees

BSTs are used to organize a set of search keys for fast access: the tree maintains the keys in-order so that comparison with the query at any node either results in a match, or directs us to continue the search in left or right sub-tree.

For this problem we are given a set of search keys (0, 1, … n) along with the search frequency count (f0, f1, …. fn) of each key. The set of keys is sorted. A BST can be constructed from such a set of keys, so that keys can be searched quickly but there’s a cost associated with the search operation on BST. Searching cost for a key/node in the BST is defined as – level of that key/node multiplied by its frequency. Level of root node is 1. Total searching cost of the BST is the sum of searching cost of all the keys/nodes in the BST. Given a set of keys the problem is to arrange the keys in a BST that minimizes the total searching cost.

For example:
Keys: {0 ,1} and Freq: {10, 20}
Possible BSTs created from this set of keys are:

```1) Total cost of BST = (level of key0 * freq of key0) +
(level of key1 * freq of key1)
= (1 * 10) + (2 * 20)
= 50
2) Total cost of BST = (level of key1 * freq of key1) +
(level of key0 * freq of key0)
= (1 * 20) + (2 * 10)
= 40 ```

Hence, the minimum total searching cost for given set of keys is 40.

## Thought Process:

As per definition of searching cost for a key in the BST – (level of key (L) * freq of key (F)), here we can observe that starting from level ‘1’ till level ‘L’ at each level the key contributes ‘F’ to the total cost and that’s why its searching cost is (L * F).

In order to minimize the total search cost, a simple Greedy approach comes to mind where we try to keep keys with higher frequency at the top of the tree like we choose the key with highest frequency as root, then from the keys on the left of it we again choose a key with highest frequency and make it the left child of root and similarly we choose the right child of the root from the keys on the right and build a BST.

But will this approach build a BST that give minimum total search cost? To prove a Greedy approach works, we have to give a proof. But to prove a Greedy approach fails, we just have to give an example where it doesn’t work.

Let’s consider this example:

Using the Greedy approach discussed above let’s build a BST and calculate its total cost:
Key ‘4’ has highest frequency: 25, so it will be the root. Keys {0,…,3} will be used to build the left sub-tree and keys {5, 6} will be used to build the right sub-tree.
Among keys {0,…,3}, key ‘0’ has the highest frequency, hence it will be the left child of the root.
Among keys {5, 6}, key ‘6’ has the highest frequency, hence it will be the right child of the root.
We keep doing this all the remaining keys and the final BST would look like this:

```If Level of Key(k) is Lk and Frequency of Key(k) is Fk, then -

Total cost of Greedy BST = (L4 * F4)+(L0 * F0)+(L6 * F6)+
(L2 * F2)+(L5 * F5)+(L1 * F1)+
(L3 * F3)
= (1 * 25)+(2 * 22)+(2 * 8) +
(3 * 20)+(3 * 2) +(4 * 18)+
(4 * 5)
= 243```

But is there any other possible BST that has lower total searching cost?
Let’s consider this BST:

```Total cost of this BST = (1 * 20) + (2 * 22) + (2 * 25) +
(3 * 18) + (3 * 5) + (3 * 8) +
(4 * 2)
= 215```

This BST has lower total cost (215) than the BST created using Greedy approach (243). Hence the Greedy approach fails to solve this problem. But then how do we find the optimal BST?

## Solution:

Let’s consider a given set of keys {Ki, … , Kj} and Min_Total_Cost(i, j) returns the total searching cost for the optimal BST for this set.
Let’s say we have created the optimal BST for this set of keys and ‘Kr’ is the root of this BST such that i <= r <= j, the tree would look like this:

Kr

/ \

Ki,…, Kr-1    Kr+1,…, Kj

The keys on the left of Kr in the given set will be part of left sub-tree and the keys on the right will be part of right sub-tree. If Total_Cost(i, j) gives the total searching cost for this BST, then it includes –

1. The searching cost of the root which is – level of root (1) * frequency of root key,
2. The total cost of the left sub-tree and the total cost of the right sub-tree (the sub-problems),
3. And as explained earlier that making the keys on the left and right of Kr in the given set the children of Kr will increase their path length by 1 and hence all these keys will incur that cost to the total cost, i.e. all keys which are yet to be included in the BST contribute a cost equal to their frequency to the total cost at every level, hence at each level we have sum of frequency of all such keys/nodes.
```Total_Cost(i, j) =  (Level of Kr * Freq of Kr)
+(Total searching cost of left sub-tree)
+(Total searching cost of right sub-tree)
+(Sum of frequency of all the keys in the
left sub-tree)
+(Sum of frequency of all the keys in the
right sub-tree)

= Total_Cost(i, r-1) +
Total_Cost(r+1, j) +
(Sum of frequency of all the keys {Ki,…,
Kj})```

Since we do not know the key Kr, we will have to try out each key in the set as root of the BST and we will keep track of the minimum of the total searching cost of the BSTs as we calculate them.
Using this formula above we can write for Min_Total_Cost(i, j) as –

```Min_Total_Cost(i, j) = min ( Min_Total_Cost(i, r-1)
+ Min_Total_Cost(r+1, j)
+ Sum of all Fx for x in
{i,..,j} )
for all r in {i,..,j}

If i > j which doesn’t make a valid set of keys, Min_Total_Cost(i, j) = 0.```

Also this shows this problem has optimal substructure (i.e. an optimal solution can be constructed from optimal solutions of subproblems).

### Recursive Approach:

Using this we can write a recursive implementation:

C++:

```#include <bits/stdc++.h>
using namespace std;

int Min_Total_Cost(int freq[], int i, int j)
{
if (i > j)
return 0;

int min_total_cost = INT_MAX;

for (int k = i; k <= j; ++k)
{
int total_cost = ( Min_Total_Cost(freq, i, k-1)
+ Min_Total_Cost(freq, k+1, j)
+ accumulate(freq+i, freq+j+1, 0));

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

return min_total_cost;
}

int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
return Min_Total_Cost(freq, 0, num_keys-1);
}

int main()
{
int keys[] = {0, 1, 2};
int freq[] = {34, 8, 50};
int n = sizeof(keys) / sizeof(keys);

cout<<"Total cost of Optimal BST:"<<getTotalCostOfOptimalBST(keys, freq, n)<<endl;

return 0;
}```

Java:

```import java.io.*;

class OptimalBST
{
static int sum(int freq[], int left_idx, int right_idx)
{
int sum = 0;
for (int i=left_idx; i <= right_idx; ++i)
{
sum += freq[i];
}
return sum;
}

static int Min_Total_Cost(int freq[], int i, int j)
{
if (i > j)
return 0;

int min_total_cost = Integer.MAX_VALUE;

for (int k = i; k <= j; ++k)
{
int total_cost = ( Min_Total_Cost(freq, i, k-1)
+ Min_Total_Cost(freq, k+1, j)
+ sum(freq, i, j));

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

return min_total_cost;
}

static int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
return Min_Total_Cost(freq, 0, num_keys-1);
}

public static void main (String[] args)
{
int keys[] = {0, 1, 2};
int freq[] = {34, 8, 50};
int n = keys.length;

System.out.println("Total cost of Optimal BST:" +
getTotalCostOfOptimalBST(keys, freq, n));
}
}```

But this implementation has exponential time complexity. To find the reason behind such high time complexity let’s have a look at the recursive function call tree:

In this example of a set consisting of 3 keys {0, 1, 2}, we can see that subproblems such as  Min_Total_Cost(freq, 2, 2) and Min_Total_Cost(freq, 1, 1) are calculated repeatedly.
Our recursive algorithm for this problem solves the same subproblem over and over rather than always generating new subproblems. These are called overlapping subproblems.

As the two properties required for using Dynamic Programming : ‘optimal substructure’ and ‘overlapping subproblems’ hold, we can use DP for this problem.

### Dynamic Programming Solution:

In DP we start calculating from the bottom and move up towards the final solution.
Hence we first solve the sub-problem {i=0, j=0}, then we skip all the sub-problems where (i > j), then next we solve {i=1, j=1}, and reuse solutions to these sub-problems to solve {i=0, j=1} and so on.
Finally we solve the sub-problem {i=0, j=(n-1)} and this gives us the final answer.

Solution of all subproblems are stored in a 2D array / DP table so that they can be reused when required.

C++:

```#include <bits/stdc++.h>
using namespace std;

long long int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
long long int DP_Table[num_keys][num_keys]{};

for (int j = 0; j < num_keys; ++j)
{
for (int i = j; i >= 0; --i)
{
long long int min_total_cost = INT_MAX,
sum_freq = accumulate(freq+i, freq+j+1, 0);

for (int k = i; k <= j; ++k)
{
long long int total_cost = 0,
total_cost_left_subtree = 0,
total_cost_right_subtree = 0;

if (k > i)
{
total_cost_left_subtree = DP_Table[i][k-1];
}

if (k < j)
{
total_cost_right_subtree = DP_Table[k+1][j];
}

total_cost = ( total_cost_left_subtree
+ total_cost_right_subtree
+ sum_freq );

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

DP_Table[i][j] = min_total_cost;
}
}

return DP_Table[num_keys-1];
}

int main()
{
int keys[] = {0, 1, 2, 3, 4, 5, 6};
int freq[] = {22, 18, 20, 5, 25, 2, 8};
int num_keys = (sizeof(keys) / sizeof(keys));

cout<<"Total cost of Optimal BST:"
<<getTotalCostOfOptimalBST(keys, freq, num_keys)<<endl;

return 0;
}```

Java:

```import java.io.*;

class OptimalBST
{
static int sum(int freq[], int left_idx, int right_idx)
{
int sum = 0;
for (int i=left_idx; i <= right_idx; ++i)
sum += freq[i];
return sum;
}

static int getTotalCostOfOptimalBST(int keys[], int freq[], int num_keys)
{
int DP_Table[][] = new int[num_keys][num_keys];

for (int j = 0; j < num_keys; ++j)
{
for (int i = j; i >= 0; --i)
{
int min_total_cost = Integer.MAX_VALUE,
sum_freq = sum(freq, i, j);

for (int k = i; k <= j; ++k)
{
int total_cost = 0,
total_cost_left_subtree = 0,
total_cost_right_subtree = 0;

if (k > i)
total_cost_left_subtree = DP_Table[i][k-1];

if (k < j)
total_cost_right_subtree = DP_Table[k+1][j];

total_cost = ( total_cost_left_subtree
+ total_cost_right_subtree
+ sum_freq );

if (total_cost < min_total_cost)
min_total_cost = total_cost;
}

DP_Table[i][j] = min_total_cost;
}
}
return DP_Table[num_keys-1];
}

public static void main (String[] args)
{
int keys[] = {0, 1, 2, 3, 4, 5, 6};
int freq[] = {22, 18, 20, 5, 25, 2, 8};
int num_keys = keys.length;

System.out.println("Total cost of Optimal BST is "
+ getTotalCostOfOptimalBST(keys, freq, num_keys));
}
}```

Time complexity: O(n^3)
Space complexity: O(n^2)

# Is binary tree subtree of another binary tree

Given two binary trees s and t, find if binary tree t is subtree of binary tree s.
For example: Given binary tree s as follows, binary tree t will be a subtree as shown. target binary tree which is subtree of the source binary tree

However, if the binary tree s is as follows, then t is not a subtree of the tree s Let’s start from the ver simple cases and build on top of them. What if one of the trees is or both of them are empty? If s and t both are empty binary trees, then of course t is subtree of s.
Other case, when s is empty and t not, then t is not subtree. Similary, when t is not empty and s is empty, then also, t is not subtree of s.

``` if(s == null && t == null){
return true;
}

if(s == null || t == null){
return false;
}
```

Now, if we start from the root of both trees, there are two possibilities: First, the root of two trees match with values. `s.val == t.val`. In this case, the problem reduces to check if left subtree of target tree is same as a left subtree of the source and if right subtree of target tree is same as the right subtree of source binary tree.

```return s.val == t.val
&& isSame(s.left,t.left)
&& isSame(s.right,t.right);
```

If everything goes fine and we hit the condition when both s and t then we know that both trees are same and one should be a subtree of other.

Second, the root of the two trees are not the same? In that case, we check if left subtree of s is same as s or right subtree of s is same as t. If one of subtree same as the target tree, we return true.

```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {

if(s == null && t == null){
return true;
}

if(s != null && t == null){
return false;
}

if(s == null && t != null){
return false;
}

if(s.val != t.val) {
return (isSubtree(s.left,t.left)
&& isSubtree(s.right,t.right));
}
else {
return  isSubtree(s.left,t)
|| isSubtree(s.right,t);
}
}
}
```

Above implementation will work for the below case. but will not work for this case. This is almost done. But there is one small mistake in it. We are relying on the inequality of the root nodes. What if the current roots are equal and some nodes in left or right subtrees do not the match? We have to come up all the way where we started with s and t to check if t is a subtree of s. That is why we have two separate functions: One to check if trees are same once their roots match and other to start afresh once we find that trees are not the same starting at a particular root. Above function actually does not start from the place where we started with s and t if node values do not match and continue down the subtree. This will return true even if roots and leaves match even if intermediate nodes do not. This is the case most of the students fail to understand.

### Binary tree is subtree of another binary tree : Implementation

```
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class IsSubtree {
public boolean isSubtree(TreeNode s, TreeNode t) {

if(s == null) return false;

if(!isSame(s,t)){
return isSubtree(s.left,t)
|| isSubtree(s.right,t);
}

return true;
}

private boolean isSame(TreeNode s, TreeNode t){

if(s == null && t == null){
return true;
}

if(s == null || t == null){
return false;
}

return s.val == t.val
&& isSame(s.left,t.left)
&& isSame(s.right,t.right);
}
}
```

The complexity of implementation to find if one binary tree is a subtree of another is O(n) where n is the number of nodes in the target tree.

You can run this code on the leetcode problem and see it passes all test cases there.
Please share if there is something wrong or missing. If you are preparing for an interview and want personalized coaching, please reach out to us at [email protected] or book a free session with us.

Posted on Categories Binary Search Tree, Data StructuresLeave a comment on Is binary tree subtree of another binary tree

## Lowest common ancestor(LCA) using RMQ

We already have discussed lowest common ancestor and range minimum query. In this post, we will discuss how to use RMQ to find the lowest common ancestor of two given nodes in a binary tree or binary search tree. LCA of two nodes u and v is the node which is furthest from root and u and v are descendant of that node. For example, LCA `node(5)` and `node(9)` in below tree is `node(2)`. In earlier solutions, we scan the whole binary tree every time we have to find LCA of two nodes. This has a complexity of `O(n)` for each query. If this query if fired frequently, this operation may become a bottleneck of the algorithm. One way to avoid processing all nodes on each query is to preprocess binary tree and store precalculated information to find LCA of any two nodes in constant time.

This pattern is very similar to a range minimum query algorithm. Can we reduce the lowest common ancestor problem to range minimum query problem?

### Reduction of lowest common ancestor problem to RMQ

Let’s revise what is RMQ: Given an array A of length n; RMQ(i,j) – returns the index of the minimum element in the subarray A[i..j]. Let’s find LCA of two nodes 5 and 8 manually in the above binary tree. We notice that LCA(u,v) is a shallowest common node (in terms of distance from root) which is visited when u and v are visited using the depth-first search of the tree. An important thing to note is that we are interested in shallowest, which is minimum depth, the node between u and v. Sounds like RMQ?

Implementation wise, the tree is traversed as Euler tour, which means we visit each node of tree, without lifting the pencil. This is very similar to a preorder traversal of a tree. At most, there can be 2n-1 nodes in Euler tour of a tree with n nodes, store this tour in an array `E[1..2n-1]`.

As algorithm requires the shallowest node, closest to root, so we store the depth of each node while doing Euler tour, so we store the depth of each node in another array D[1..2n-1].

We should maintain the value when the node was visited for the first time. Why?

E[1..2n-1] – Store the nodes visited in a Euler tour of T. Euler[i] stores ith node visited in the tour.
D[1..2n-1] – Stores level of the nodes in tour. D[i] is the level of node at Euler[i]. (level is defined to be the distance from the root).
F[1..n] – F[i] will hold value when node is first visited.

For example of this graph, we start from node(1) and do Euler tour of the binary tree. Euler tour would be like Depth array is like First visit array looks like To compute LCA(u,v): All nodes in the Euler tour between the first visits to u and v are `E[F[u]...F[v]]` (assume F[u] is less than F[v] else, swap u and v). The shallowest node in this tour is at index `RMQ D(F[u]..F[v])`, since D[i] stores the depth of node at E[i].
RMQ function will return the index of the shallowest node between u and v, thus output node will be `E[RMQ D(F[u], F[v])]` as LCA(u,v)

Let’s take an example, find the lowest common ancestor of `node(5)` and `node(8)`.

First of all, find the first visit to `node(5)` and `node(8)`. It will be F which is 2 and F which is 7. Now, all the nodes which come between visit of `node(5)` and `node(8)` are in E[2..7], we have to find the shallowest node out these nodes. This can be done by applying RMQ on array D with range 3 to 6. LCA will be E[RMQ( D(2,7)], in this case, RMQ(D[2..7]) is index 3. E = 2, hence LCA(5,8) is `node(2)`. #### Lowest common ancestor using RMQ: Implementation

```package com.company.BST;

import java.util.Arrays;

/**
* Created by sangar on 1.1.19.
*/
public class LowestCommonAncestor {

private int[] E;
private int[] D;
private int[] F;

int[][] M;

private int tourCount;

public LowestCommonAncestor(BinarySearchTree tree){
//Create Euler tour, Depth array and First Visited array
E = new int[2*tree.getSize()];
D = new int[2*tree.getSize()];
F = new int[tree.getSize() + 1];

M = new int[2 * tree.getSize()][2 * tree.getSize()];

Arrays.fill(F, -1);
getEulerTour(tree.getRoot(), E, D, F, 0);

preProcess(D);
}

public int findLowestCommonAncestor(int u, int v){
//This means node is not in tree
if(u >= F.length || v >= F.length || F[u] == -1 || F[u] == -1)
return -1 ;

return E[rmq(D, F[u], F[v])];
}

/* This function does all the preprocessing on the tree and
creates all required arrays for the algorithm.
*/
private void getEulerTour(TreeNode node, int[] E, int[] D, int[] F,
int level){
if(node == null) return;

int val = (int)node.getValue();

E[tourCount] = val; // add to tour
D[tourCount] =  level; // store depth

if(F[val] == -1) {
F[(int) node.getValue()] = tourCount;
}
tourCount++;

if(node.getLeft() != null ) {
getEulerTour(node.getLeft(), E, D, F, level + 1);

E[tourCount] = val;
D[tourCount++] = level;
}
if(node.getRight() != null ) {
getEulerTour(node.getRight(), E, D, F, level + 1);

E[tourCount] = val;
D[tourCount++] = level;
}
}

/*
This function preprocess the depth array to quickly find
RMQ which is used to find shallowest node.
*/
void preProcess(int[] D) {

for (int i = 0; i < D.length; i++)
M[i] = i;

for (int j = 1; 1 << j <D.length ; j++){
for (int i = 0; i + (1 << j) - 1 < D.length; i++){
if (D[M[i][j - 1]] < D[M[i + (1 << (j - 1))][j - 1]])
M[i][j] = M[i][j - 1];
else
M[i][j] = M[i + (1 << (j - 1))][j - 1];
}
}
}

private int rmq(int a[], int start, int end){
int j = (int)Math.floor(Math.log(end-start+1));

if ( a[ M[start][j] ] <= a[M[end-(1<<j)+1][j]] )
return M[start][j];

else
return M[end-(1<<j)+1][j];
}
}
```

The beauty of this algorithm is that it can be used to find LCA of any tree, not just only binary tree or BST. The complexity of the algorithm to find a lowest common ancestor using range minimum query is `(O(n), O(1))` with an additional space complexity of `O(n)`.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free demo class to guide you through the process.

Posted on Categories Algorithms, Binary Search Tree, Data Structures, GraphLeave a comment on Lowest common ancestor(LCA) using Range Minimum Query(RMQ)

## Runway reservation system

Given an airport with a single runway, we have to design a runway reservation system of that airport. Add to details: each reservation request comes with requested landing time let’s say t. Landing can go through if there is no landing scheduled within k minutes of requested time, that means t can be added to the set of scheduling landings. K can vary and depends on external conditions. This system helps with reservations for the future landings.
Once the plane lands safely, we have to remove the plane for landing sets.

This is perfectly possible with airports with multiple runways where only one runway can be used because of weather conditions, maintenance etc. Also, one landing cannot follow another immediately due safety reasons, that’s why there has to be some minimum time before another landing takes place. We have to build this system with given constraints.

In nutshell, we have create a set of landings which are compatible with each other, i.e they do not violate the constraint put.  There are two operations to be performed on this set : insertion and removal. Insertion involves checking of constraints.

Example: let’s say below is the timeline of all the landing currently scheduled and k = 3 min

Now, if the new request comes for landing at 48.5, it should be added to the set as it does not violate the constraint of k mins. However, if a request comes for landing at 53, it cannot be added as it violates the constraint.
If a new request comes for 35, it is invalid as the request is in past.

## Reservation system: thoughts

What is the most brute force solution which comes to mind? We can store all the incoming requests in an unsorted array.  Insertion should be O(1) operation as it is at the end. However, checking the constrain that it is satisfied will take O(n) because we have to scan through the entire array.
Same is true even if we use unsorted linked list.

How about a sorted array? We can use a binary search algorithm to find the constraint, which will take O(log n) complexity. However, the insertion will still be O(n) as we have to move all the elements to the right from the position of insertion.

Sorted list solves the problem of insertion in O(1) but then search for the constraint will be O(n) complexity. It just moves the problem from one place to another.

### Reservation system using binary search tree

We have to optimize two things : first check if the new request meets the constraints, second insert the new request into the set.

Let’s think of binary search tree. To check a constraint, we have to check each node of the binary tree, but based on the relationship of the current node and the new request time, we can discard half of the tree. (Binary search tree property, where all the nodes on the left side are smaller than the root node and all the nodes on the right side are greater than the current node)

When a new request comes, we check with the root node and it does not violate the constraints, then we check if the requested time is less than the root. If yes, we go to left subtree and check there. If requested landing time is greater than the root node, we go to right subtree.
When we reach the leaf node, we add a new node with new landing time as the value of that node.

If at any given node, the constraint is violated, i.e not new landing time is within k minutes of time in the node, then we just return stating it is not possible to add new landing.

What will be complexity of checking the constraint? It will be O(h) where h is height of binary search tree. Insert is then O(1) operation.

#### Reservation system implementation

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

void inoderTraversal(Node * root){
if(!root) return;

inoderTraversal(root->left);
printf("%d ", root->value);
inoderTraversal(root->right);
}

Node *createNode(int value){
Node * newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}

Node *addNode(Node *node, int value, int K){
if(!node)
return createNode(value);

if ( node->value + K > value && node->value - K < value ){
return node;
}
if (node->value > value)
else
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;

//Creating a binary tree
inoderTraversal(root);

return 0;
}

```

Let’s say a new requirement comes which is to find how many flights are scheduled till time t?

This problem can easily be solved using binary search tree, by keeping track of size of subtree at each node as shown in figure below.

While inserting a new node, update counter of all the nodes on the nodes. When query is run, just return the count of node of that time or closest and smaller than that value of t.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup to receive free preparation material.

## Prune nodes not on paths with given sum

Prune nodes not on paths with given sum is a very commonly asked question in Amazon interviews. It involves two concepts in one problem. First, how to find a path with a given sum and then second, how to prune nodes from binary tree. The problem statement is:

Given a binary tree, prune nodes which are not paths with a given sum.

For example, given the below binary tree and given sum as 43, red nodes will be pruned as they are not the paths with sum 43.

### Prune nodes in a binary tree: thoughts

To solve this problem, first, understand how to find paths with a given sum in a binary tree.  To prune all nodes which are not on these paths,  get all the nodes which are not part of any path and then delete those nodes one by one. It requires two traversals of the binary tree.
Is it possible to delete a node while calculating the path with a given sum? At what point we find that this is not the path with given sum? At the leaf node.
Once we know that this leaf node is not part of the path with given sum, we can safely delete it.  What happens to this leaf node? We directly cannot delete the parent node as there may be another subtree which leads to a path with the given sum. Hence for every node, the pruning is dependent on what comes up from its subtrees processing.

At the leaf node, we return to parent false if this leaf node cannot be part of the path and delete the leaf node. At parent node, we look for return values from both the subtrees. If both subtrees return false, it means this node is not part of the path with the given sum. If one of the subtrees returns true, it means the current node is part of a path with the given sum. It should not be deleted and should return true to its parent.

#### Prune nodes from a binary tree: implementation

```#include<stdio.h>
#include<stdlib.h>
#include<math.h>

struct node{
int value;
struct node *left;
struct node *right;
};
typedef struct node Node;

#define true 1
#define false 0

int prunePath(Node *node, int sum ){

if( !node ) return true;

int subSum =  sum - node->value;
/* To check if left tree or right sub tree
contributes to total sum  */

int leftVal = false, rightVal = false;

/*Check if node is leaf node */
int isLeaf = !( node->left || node->right );

/* If node is leaf node and it is part of path with sum
= given sum return true to parent node so tha parent node is
not deleted */
if(isLeaf && !subSum )
return true;

/* If node is leaf and it not part of path with sum
equals to given sum
Return false to parent node */
else if(isLeaf && subSum ){
free(node);
return false;
}
/* If node is not leaf and there is left child
Traverse to left subtree*/
leftVal = prunePath(node->left, subSum);

/* If node is not leaf and there is right child
Traverse to right subtree*/
rightVal = prunePath(node->right, subSum);

/* This is crux of algo.
1. If both left sub tree and right sub tree cannot lead to
path with given sum,Delete the node
2. If any one sub tree can lead to path with sum equal
to given sum, do not delete the node */
if(!(leftVal || rightVal) ){
free(node);
return false;
}
if(leftVal || rightVal ){
if(leftVal)
node->right = NULL;
if(rightVal)
node->left = NULL;
return true;
}
return true ;
}

void inoderTraversal(Node * root){
if(!root)
return;

inoderTraversal(root->left);
printf("%d ", root->value);
inoderTraversal(root->right);
}
Node *createNode(int value){
Node * newNode =  (Node *)malloc(sizeof(Node));
newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;
}
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
//Creating a binary tree

inoderTraversal(root);
prunePath(root, 65);

printf( "\n");
if( root ){
inoderTraversal(root);
}
return 0;
}

```

The complexity of this algorithm to prune all nodes which are not on the path with a given sum is O(n).

## Print paths in a binary tree

We learned various kind of traversals of a binary tree like inorder, preorder and postorder. Paths in a binary tree problem require traversal of a binary tree too like every other problem on a binary tree. The problem statement is:

Given a binary tree, print all paths in that binary tree

What is a path in a binary tree? A path is a collection of nodes from the root to any leaf of the tree. By definition, a leaf node is a node which does not have left or right child. For example, one of the paths in the binary tree below is 10,7,9.

### Paths in a binary tree: thoughts

It is clear from the problem statement that we have to start with root and go all the way to leaf nodes. Question is do we need to start with root from each access each path in binary tree? Well, no. Paths have common nodes in them. Once we reach the end of a path (leaf node), we just move upwards one node at a time and explore other paths from the parent node. Once all paths are explored, we go one level again and explore all paths from there.

This is a typical postorder traversal of a binary tree, we finish the paths in the left subtree of a node before exploring paths on the right subtree We process the root before going into left or right subtree to check if it is the leaf node. We add the current node into the path till now. Once we have explored left and right subtree, the current node is removed from the path.

Let’s take an example and see how does it work. Below is the tree for each we have to print all the paths in it.

First of all our list of paths is empty. We have to create a current path, we start from the root node which is the `node(10)`. Add `node(10)` to the current path. As `node(10)` is not a leaf node, we move towards the left subtree.

`node(7)` is added to the current path. Also, it is not a leaf node either, so we again go down the left subtree.

`node(8)` is added to the current path and this time, it is a leaf node. We put the entire path into the list of paths or print the entire path based on how we want the output.

At this point, we take out`node(8)` from the current path and move up to node(7). As we have traversed the left subtree of,`node(7)` we will traverse right subtree of the node(7).

`node(9)` is added now to the current path. It is also a leaf node, so again, put the path in the list of paths. `node(9)` is moved out of the current path.

Now, left and right subtrees of `node(7)` have been traversed, we remove `node(7)` from the current path too.

At this point, we have only one node in the current path which is the `node(10)` We have already traversed the left subtree of it. So, we will start traversing the right subtree, next we will visit `node(15)` and add it to the current path.

`node(15)` is not a leaf node, so we move down the left subtree. node(18) is added to the current path. `node(18)` is a leaf node too. So, add the entire path to the list of paths. Remove `node(18)` from the current path.

We go next to the right subtree of the `node(15)`, which is the `node(19)`. It is added to the current path. `node(19)` is also a leaf node, so the path is added to the list of paths.

Now, the left and right subtrees of the `node(15)` are traversed, it is removed from the current path and so is the `node(10)`.

#### Print paths in a binary tree: implementation

```package com.company.BST;

import java.util.ArrayList;

/**
* Created by sangar on 21.10.18.
*/
public class PrintPathInBST {
public void printPath(BinarySearchTree tree){
ArrayList<TreeNode> path  = new ArrayList<>();
this.printPathRecursive(tree.getRoot(), path);
}

private void printPathRecursive(TreeNode root,
ArrayList<TreeNode> path){
if(root == null) return;

//If node is leaf node
if(root.getLeft() == null && root.getRight() == null){
path.forEach(node -> System.out.print(" "
+ node.getValue()));
path.remove(path.size()-1);
System.out.println();
return;
}

/*Not a leaf node, add this node to
path and continue traverse */
printPathRecursive(root.getLeft(),path);
printPathRecursive(root.getRight(), path);

//Remove the root node from the path
path.remove(path.size()-1);
}
}
```

Test cases

```package com.company.BST;

/**
* Created by sangar on 10.5.18.
*/
public class BinarySearchTreeTests {
public static void main (String[] args){
BinarySearchTree binarySearchTree = new BinarySearchTree();

binarySearchTree.insert(7);
binarySearchTree.insert(8);
binarySearchTree.insert(6);
binarySearchTree.insert(9);
binarySearchTree.insert(3);
binarySearchTree.insert(4);

binarySearchTree.printPath();
}
}
```

Tree node definition

```package com.company.BST;

/**
* Created by sangar on 21.10.18.
*/
public class TreeNode<T> {
private T value;
private TreeNode left;
private TreeNode right;

public TreeNode(T value) {
this.value = value;
this.left = null;
this.right = null;
}

public T getValue(){
return this.value;
}
public TreeNode getRight(){
return this.right;
}
public TreeNode getLeft(){
return this.left;
}

public void setValue(T value){
this.value = value;
}

public void setRight(TreeNode node){
this.right = node;
}

public void setLeft(TreeNode node){
this.left = node;
}
}

```

Complexity of above algorithm to print all paths in a binary tree is O(n).

# Inorder predecessor in binary search tree

What is an inorder predecessor in binary tree? Inorder predecessor is the node which traversed before given node in inorder traversal of binary tree.  In binary search tree, it’s the previous big value before a node. For example, inorder predecessor of node(6) in below tree will 5 and for node(10) it’s 6. If node is leftmost node in BST or least node, then there is no inorder predecessor for that node.

## Inorder predecessor : Thoughts

To find inorder predecessor , first thing to find is the node itself.  As we know in inorder traversal, root node is visited after left subtree.  A node can be predecessor for given node which is on right side of it.

Let’s come up with examples and see what algorithm works. First case, if given node is left most leaf node of tree, there is no inorder predecessor, in that case return NULL. For example, predecessor for node 1 is NULL. What if node has left subtree? In that case, maximum value in left subtree will be predecessor of given node.  We can find maximum value in tree by going deep down right subtree, till right subtree is NULL, and then return the last node. For example, predecessor node(10) is 6. What are the other cases? Another case is that node does not have left subtree but it is also not the leftmost leaf node? Then parent of given node will be inorder predecessor. While moving down the tree on right side, keep track of parent node as it may be solution. predecessor of node(12) will be 10 as that’s where we moved to right subtree last time.  Note that we change predecessor candidate only  while moving down right subtree. ### Algorithm to find inorder predecessor

2. If `node.value` > `current.value`, then predecessor = current, current = current.right.
3. If `node.value` < `current.value`, current = current.left.
4. If `node.value` == `current.value` and node.left!= null, predecessor = maximum(current.left).
5. Return predecessor

### Inorder predevessor: Implementation

```#include<stdio.h>
#include<stdlib.h>

struct node{
int value;
struct node *left;
struct node *right;
};

typedef struct node Node;

/* This function return the maximum node in tree rooted at node root */
Node *findMaximum(Node *root){
if(!root)
return NULL;

while(root->right) root = root->right;
return root;
}
/* This function implements the logic described in algorithm to find inorder predecessor
of a given node */
Node *inorderPredecessor(Node *root, int K){

Node *predecessor 	= NULL;
Node *current  		= root;

if(!root)
return NULL;

while(current && current->value != K){
/* Else take left turn and no need to update predecessor pointer */
if(current->value >K){
current= current->left;
}
/* If node value is less than the node which are looking for, then go to right sub tree
Also when we move right, update the predecessor pointer to keep track of last right turn */
else{
predecessor = current;
current = current->right;
}
}
/*Once we reached at the node for which inorder predecessor is to be found,
check if it has left sub tree, if yes then find the maximum in that right sub tree and return that node
Else last right turn taken node is already stored in predecessor pointer and will be returned*/
if(current && current->left){
predecessor = findMaximum(current->left);
}
return predecessor;
}
Node * createNode(int value){
Node *newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;

}

Node * addNode(Node *node, int value){
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
int n = 0;
//Creating a binary tree

Node *predecessor = inorderPredecessor(root, 40);
printf("\n Inorder successor node is : %d ",predecessor ? predecessor->value: 0);

return 0;
}
```

Complexity of algorithm to find inorder predecessor will be O(logN) in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N).

Please share if there is something wrong or missing. If you want to contribute to website and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]

Posted on Categories Binary Search Tree, Data Structures1 Comment on Inorder predecessor in binary search tree

# Inorder successor in binary search tree

What is an inorder successor in binary tree? Inorder successor is the node which traversed next to given node in inorder traversal of binary tree.  In binary search tree, it’s the next big value after the node. For example, inorder successor of node(6) in below tree will 10 and for node(12) it’s 14. If node is the rightmost node or in BST, the greatest node, then there is no inorder successor for that node.

## Inorder successor : Thoughts

To find inorder successor, first thing to find is the node itself.  As we know in inorder traversal, root node is visited after left subtree.  A node can be successor for given node which is on left side of it.

Let’s come up with examples and see what algorithm works. First case, if the node is right most node of tree, there is no inorder successor, in that case return NULL. For example, successor for node 16 is NULL. What if node has right subtree? In that case, minimum value in right subtree will be successor of given node.  We can find minimum value in tree by going deep down left subtree, till left subtree is NULL, and then return the last node. For example, successor node(5) is 6. What are the other cases? Another case is that node does not have right subtree? Then parent of given node will be inorder successor. While moving down the tree on left side, keep track of parent node as it may be the solution. Successor of node(7) will be 10 as that’s where we moved to left subtree last time.  Note that we change successor candidate only  while moving down left subtree. ### Algorithm to find inorder successor

2. If `node.value` < `current.value`, then successor = current, current = current.left.
3. If `node.value` > `current.value`, current = current.right.
4. If `node.value` == `current.value` and node.right != null, successor = minimum(current.right).
5. Return successor

### Inorder successor : Implementation

```#include<stdio.h>
#include<stdlib.h>

struct node{
int value;
struct node *left;
struct node *right;
};

typedef struct node Node;

//this function finds the minimum node in given tree rooted at node root
Node * findMinimum(Node *root){
if(!root)
return NULL;
// Minimum node is left most child. hence traverse down till left most node of tree.
while(root->left) root = root->left;
// return the left most node
return root;
}
/* This function implements the logic described in algorithm to find inorder successor
of a given node */
Node *inorderSuccessor(Node *root, Node *node){

Node *successor = NULL;
Node *current  = root;
if(!root)
return NULL;

while(current->value != node->value){
/* If node value is greater than the node which are looking for, then go to left sub tree
Also when we move left, update the successor pointer to keep track of lst left turn */

if(current->value > node->value){
successor = current;
current= current->left;
}
/* Else take right turn and no need to update successor pointer */
else
current = current->right;
}
/*Once we reached at the node for which inorder successor is to be found,
check if it has right sub tree, if yes then find the minimum in that right sub tree and return taht node
Else last left turn taken node is already stored in successor pointer and will be returned*/
if(current && current->right){
successor = findMinimum(current->right);
}

return successor;
}

Node * createNode(int value){
Node *newNode =  (Node *)malloc(sizeof(Node));

newNode->value = value;
newNode->right= NULL;
newNode->left = NULL;

return newNode;

}

Node * addNode(Node *node, int value){
if(node == NULL){
return createNode(value);
}
else{
if (node->value > value){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
int n = 0;
//Creating a binary tree
Node *node = root;

Node *successor = inorderSuccessor(root, node);
printf("\n Inorder successor node is : %d ",successor ? successor->value: 0);

return 0;
}

```

Complexity of algorithm to find inorder successor will be O(logN) in almost balanced binary tree. If tree is skewed, then we have worst case complexity of O(N).

Please share if there is something wrong or missing. If you want to contribute to website and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]

Posted on Categories Binary Search Tree, Data Structures1 Comment on Inorder successor in binary search tree

## Iterative postorder traversal

In last two posts, iterative inorder and iterative preorder traversal, we learned how stack can be used to replace recursion and why recursive implementation can be dangerous in production environment. In this post, let’s discuss iterative postorder traversal of binary tree which is most complex of all traversals. What is post order traversal ? A traversal where  left and right subtrees are visited before root is processed. For example, post order traversal of below tree would be : [1,6,5,12,16,14,10] ## Iterative postorder traversal  : Thoughts

Let’s look at the recursive implementation of postorder.

```    private void postOrder(Node root){
if(root == null) return;

postOrder(root.left);
postOrder(root.right);
System.out.println(root.value);

}
```

As we are going into left subtree and then directly to right subtree, without visiting root node. Can you find the similarity of structure between preorder and postorder implementation?  Can we reverse the entire preorder traversal to get post order traversal? Reverse preorder will give us right child, left child and then root node, however order expected is left child, right child and root child.
Do you remember we pushed left and right node onto stack in order where right child went before left. How about reversing that?

There is one more problem with just reversing the preorder. In preorder, a node was processed as soon as popped from stack, like root node will  be the first node to be processed. However, in postorder, root node is processed last. So, we actually need the order of processing too be reversed. What better than using a stack to store the reverse order of root nodes to processed.
All in all, we will be using two stacks, one to store left and right child, second to store processing order of nodes.

1. Create two stacks s an out and push root node onto s
2. While stack s is not empty
1. op from stack s, `current `= s.pop
2. Put `current` onto stack out.
3. Put left and right child of `current` on to stack s
3. Pop everything from out stack and process it.

### Postorder traversal with two stacks : Implementation

```package com.company.BST;

import java.util.Stack;

/**
* Created by sangar on 22.5.18.
*/
public class BinarySearchTreeTraversal {

private Node root;

public void BinarySearchTree(){
root = null;
}

public class Node {
private int value;
private Node left;
private Node right;

public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}

public void insert(int value){
this.root =  insertNode(this.root, value);
}

private Node insertNode(Node root, int value){
if(root == null){
//if this node is root of tree
root = new Node(value);
}
else{
if(root.value > value){
//If root is greater than value, node should be added to left subtree
root.left = insertNode(root.left, value);
}
else{
//If root is less than value, node should be added to right subtree
root.right = insertNode(root.right, value);
}
}
return root;
}
private void postOrder(Node root){
if(root == null) return;

postOrder(root.left);
postOrder(root.right);
System.out.println(root.value);
}

public void postOrderTraversal(){
postOrderIterative(root);
}

private void postOrderIterative(Node root){
Stack<Node> out = new Stack<>();
Stack<Node> s = new Stack<>();

s.push(root);

while(!s.empty()){
Node current = s.pop();

out.push(current);
if(current.left != null) s.push(current.left);
if(current.right != null) s.push(current.right);
}

while(!out.empty()){
System.out.println(out.pop().value);
}
}
}

```

Complexity of iterative implementation is O(n) with additional space complexity of O(n).

Can we avoid using two stack, and do it with one stack? Problem with root in postorder traversal is that it is visited three times, moving down from parent, coming up from left child and coming up from right child. When should be the node processed? Well, when we are coming up from right child.

How can we keep track of how the current node was reached? If we keep previous pointer, there are three cases:

1. Previous node is parent of current node, we reached node from parent node, nothing is done.
2. Previous node is left child of current node, it means we have visited left child, but still not visited right child, move to right child of current node.
3. Previous node is right child of current node, it means  we have visited left and right child of current node,  process the current node.

Let’s formulate  postorder traversal algorithm then.

1. Push root node onto stack s, set prev = null.
2. Repeat below steps till stack is not empty (!s.empty())
3. `current `= s.pop(), pop from the stack.
4. If (`prev` == null || `prev.left` == current || `prev.right` == current) then
1. If current.left != null, push `current.left` onto stack.
2. If current.right != null, push `current.right` onto stack.
3. If current.left == current.right == null, process `current`.
5. If current.left == prev, i.e. moving up left child then
1. If current.right == null, process `current`.
2. If current.right != null, push it to stack.
6. If current.right == prev i.e moving up from right child
1. process `current`.
2. prev = current, current = s.pop.

### Iterative Postorder traversal : Implementation

```package com.company.BST;

import java.util.Stack;

/**
* Created by sangar on 22.5.18.
*/
public class BinarySearchTreeTraversal {

private Node root;

public void BinarySearchTree(){
root = null;
}

public class Node {
private int value;
private Node left;
private Node right;

public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}

public void insert(int value){
this.root =  insertNode(this.root, value);
}

private Node insertNode(Node root, int value){
if(root == null){
//if this node is root of tree
root = new Node(value);
}
else{
if(root.value > value){
//If root is greater than value, node should be added to left subtree
root.left = insertNode(root.left, value);
}
else{
//If root is less than value, node should be added to right subtree
root.right = insertNode(root.right, value);
}
}
return root;
}

private void inorder(Node root){
if(root == null) return;

if(root.left != null) inorder(root.left);
System.out.println(root.value);
if(root.right != null) inorder(root.right);
}

private void preOrder(Node root){
if(root == null) return;

System.out.println(root.value);
preOrder(root.left);
preOrder(root.right);
}

private void postOrder(Node root){
if(root == null) return;

postOrder(root.left);
postOrder(root.right);
System.out.println(root.value);

}
public void postOrderTraversal(){
//  postOrder(root);
postOrderIterative2(root);
//postOrderIterative(root);
}

private void postOrderIterative2(Node root){
Node prev = null;
Stack<Node> s = new Stack<>();

s.push(root);

while(!s.empty()){
Node current  = s.peek();
if(prev == null || ( prev.left == current || prev.right == current )){
if(current.left != null) s.push(current.left);
else if(current.right != null) s.push(current.right);
}
else if(prev == current.left){
if(current.right != null) s.push(current.right);
}else{
System.out.println(current.value);
s.pop();
}

prev = current;
}
}

}

```

Complexity of code is O(n) again, with additional space complexity of O(n).

Please share if there is something wrong or missing. If you want to contribute and share your learning with thousands of learners across the world, please reach out to us at [email protected]

Posted on Categories Binary Search Tree, Data Structures2 Comments on Iterative postorder traversal

## Iterative preorder traversal

In last post Iterative inorder traversal , we learned how to do inorder traversal of binary tree without recursion or in iterative way. Today we will learn how to do iterative preorder traversal of binary tree. In preorder traversal, root node is processed before left and right subtrees. For example, preorder traversal of below tree would be [10,5,1,6,14,12,15], We already know how to implement preorder traversal in recursive way, let’s understand how to implement it in non-recursive way.

## Thought process for preorder traversal

If we look at recursive implementation, preorder traversal is: process the root, left subtree, and then right subtree.

Once the left subtree is processed, control goes to the first node in the right subtree. To emulate this behavior in a non-recursive way, it is best to use a stack. What and when push and pop will happen on the stack?
Start with pushing the root node to stack. Traversal continues till there is at least one node onto the stack.

Pop the root node from stack,process it and push it’s right and left child on to stack. Why right child before left child? Because we want to process left subtree before right subtree. As at every node, we push it’s children onto stack, entire left subtree of node will be processed before right child is popped from the stack. Algorithm is very simple and is as follows.

2. While there stack is not empty
1. Pop from stack `current ` = s.pop() and process the node.
2. Push `current.right` onto to stack.
3. Push `current.left` onto to stack.

Let’s take and example and see how it works. Given below tree, do preorder traversal on it without recursion. Let’s start from root node(10) and push it onto stack. current = node(10). Here loop starts, which checks if there is node onto stack. If yes, it pops that out. s.pop will return node(10), we will print it and push it’s right and left child onto stack. Preorder traversal till now : . Since stack is not empty, pop from it.current= node(5). Print it and push it’s right and left child i.e node(6) and node(1) on stack. Again, stack is not empty, pop from stack. current  = node(1). Print node. There is no right and left child for this node, so we will not push anything on the stack. Stack is not empty yet, pop again. current= node(6). Print node. Similar to node(1), it also does not have right or left subtree, so nothing gets pushed onto stack. However, stack is not empty yet. Pop. Current = node(14). Print node, and as there are left and right children, push them onto the stack as a right child before left child. Stack is not empty, so pop from stack, current = node(12). Print it, as there are no children of node(12), push nothing to stack. Pop again from the stack as it not empty. current = node(15). Print it. No children, so no need to push anything. At this point, the stack becomes empty and we have traversed all node of the tree also.

### Implementation

``` public void preorder(TreeNode root){
Stack<TreeNode> stack = new Stack<>();

if(root == null) return ;

TreeNode currentNode = null;
stack.push(root);

while(!stack.isEmpty()){
/* Step 5 : Pop the node */
currentNode = stack.pop();

/* Step 2 : Print the node */
System.out.println(currentNode.getValue());

/* Step 3: Push right child first */
if(currentNode.getRight() != null){
stack.push(currentNode.getRight());
}
/* Step 4: Push left child */
if(currentNode.getLeft() != null){
stack.push(currentNode.getLeft());
}
}
}
```

The complexity of iterative implementation of preorder traversal of a binary tree is O(n) as we will be visiting each node at least once. Also, there is added space complexity of stack which is O(n).

Please share if there is something wrong or missing. If you are willing to contribute and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]

Posted on Categories Binary Search Tree, Data Structures4 Comments on Iterative preorder traversal