Identical binary trees

Identical binary trees

Given two binary trees, check if two trees are identical binary trees? First question arises : when do you call two binary trees are identical? If root of two trees is equal and their left and right subtrees are also identical, then two trees are called as identical binary trees. For example, two trees below are identical.

identical binary trees

whereas these two trees are not identical as node  6 and 8 differ as well as node 14 and 16.

identical binary trees

Identical binary trees : Thoughts

Solution to the problem lies in the definition of identical tree itself. We check if roots are equal, if there are not, there is no point continue down the tree, just return that trees are not identical.
If roots are equal, we have to check is subtrees are equal. To do, so take left subtrees of both original trees and validate if left subtrees are identical too. If not, return negative response. If yes, check if right subtrees are identical too.

Did you notice two things? First, that solution to original problem depends on solution of subtrees and at each node problem reduces itself to smaller subproblem.
Second,  processing order is preorder, we process roots of two trees, then left subtrees and at last right subtree. As Mirror binary search tree and Delete binary search tree are solved using postorder traversal, this problem can be solved using preorder traversal with special processing at root node.

We can also solve it by postorder traversal too, in that case, we will be unnecessary scanning subtrees even when roots themselves are not equal.

Identical binary trees : example

Let’s take an example and see how it works. Start with root nodes, both roots are equal, move down to left subtree.

Left node in both subtrees is node(5), which is again equal. Go down the left subtree.

Again, left nodes in both subtrees is node(1), move down the left subtrees of both.

As per definition, two empty binary trees are identical. So when we move down the left child of nodes, they are null, hence identical and we return true to parent node(1). Same is true for right child.

We already know that at node(1), left and right subtree are identical, as well as node values are equal, we return true to parent node(5).

Left subtrees of node(5) are identical, move to right subtree to node(6). Similar to node(1), it also return true to parent node.

At node(5), left and right subtrees are identical, and also node values are equal, we return true to node(10).

is identical bst

Left subtrees are identical, now go to right subtree of node(10) in both trees.

is identical binary tree

Node(14) are equal in both trees, so check left subtrees of node(14) of both trees are identical. Both left subtree and right subtree of node(14) identical, same as node(1) and node(6) in left subtree, so they return true to parent node(14).

identical binary search tree

Now, at node(14), left and right subtrees are identical, so return true up to parent node(10).

Now, at  root node of both trees, there left subtrees and right subtrees are identical, so we return true for question if these two trees are identical or not.

Can you draw non identical binary trees and come up with flow and determine when they will be called out to be non-identical?

Identical binary trees : 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

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){
    if(!node) return createNode(value);
    
    if (node->value > value)
        node->left = addNode(node->left, value);
    else
        node->right = addNode(node->right, value);
    
    return node;
}

int isIdenticalBST( Node * firstTree, Node *secondTree){
    if( ! (firstTree || secondTree ) ) //both of them are empty
        return true;
    
    if( !( firstTree && secondTree ) ) // one of them is empty
        return false;
    
    return ( firstTree->value == secondTree->value )
        && isIdenticalBST( firstTree->left, secondTree->left )
        && isIdenticalBST( firstTree->right, secondTree->right );
}

/* Driver program for the function written above */
int main(){
    Node *firstRoot = NULL;
	
    //Creating a binary tree
    firstRoot = addNode(firstRoot, 30);
    firstRoot = addNode(firstRoot, 20);
    firstRoot = addNode(firstRoot, 15);
    firstRoot = addNode(firstRoot, 25);
    firstRoot = addNode(firstRoot, 40);
    firstRoot = addNode(firstRoot, 38);
    firstRoot = addNode(firstRoot, 45);
    
    printf("Inorder traversal of tree is : ");
    inoderTraversal(firstRoot);
	
    printf("\n");
    
    Node *secondRoot = NULL;
    
    //Creating a binary tree
    secondRoot = addNode(secondRoot, 30);
    secondRoot = addNode(secondRoot, 20);
    secondRoot = addNode(secondRoot, 15);
    secondRoot = addNode(secondRoot, 25);
    secondRoot = addNode(secondRoot, 40);
    secondRoot = addNode(secondRoot, 38);
    secondRoot = addNode(secondRoot, 45);
    
    printf("Inorder traversal of tree is : ");
    inoderTraversal(secondRoot);
    printf("\n");
    
    printf( "Two trees are identical : %s" , 
           isIdenticalBST( firstRoot, secondRoot ) ? "True" :"false");

    return 0;
}

Complexity to find if two trees are identical binary trees is O(n) where n is number of trees in smaller tree.

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 communications@algorithmsandme.com

Height of binary tree

Height of binary tree

One of the most basic problems on binary search tree is to find height of binary search tree or binary tree. First of all, what do we mean by height of binary search tree or height of binary tree? Height of tree is the maximum distance between the root node and any leaf node of the tree. For example, height of tree given below is 5, distance between node(10) and node(8). Note that we have multiple lea nodes, however we chose the node which s farthest from the root node.

height of binary tree

Height of binary tree : Thoughts

Brute force method to find height will be to calculate distance of each node from the root and take the maximum of it. As we will traversing each node of tree complexity will be O(n) and we need O(2logn) space to store distance for each leaf node.

What if we go bottom up instead of measuring distance of leaf nodes from root? What will be height of leaf node? At leaf node, there is no tree below it, hence height should be 1, which is node itself. What will be height of empty tree where root itself is null? It will be zero.
What if a node has a left subtree? Then height of subtree at that node will be height of left subtree + 1 (for the node itself). Same is true if node has only right subtree.

Interesting case is when node has both left and right subtree. Which height we should take to get height of subtree at node? As we are looking for maximum distance, we should take maximum of both subtrees and add 1 to get height at that node.

As we are going bottom up and building the height up from leaf to node, it is necessary to pass on height of left subtree and right subtree to root node. It means we have to process subtrees before root node. What kind of traversal is it? As in Delete binary search tree and Mirror binary search tree this problem is also postorder traversal of binary tree with specific processing at root node.

Let’s take and example and see how this method works? Given below binary tree,find height of it.

height of binary tree

We have to start from bottom and for that follow the path till node is current node is null. At root node(10), is it node null? No, then move down the left subtree.

Is node(5) null? Nope, again move down to left subtree.

At node(4), it is not null, hence we move down to left subtree. But as left child of node(4) is null, it we will return 0 as height of an empty binary tree should be 0. Again, node(4) does not even have right child, so from right side too it gets a zero. What will be height of node(40) then? Max(0,0 ) + 1 = 1, which it returns back to parent node(5).

Back at node(5), we go the height of left subtree, there is right subtree too, so we will find height of it, before judging the height of subtree at node(5). So move down the right side of node(5).

Node(7) is not null, so move down the left subtree of it, which is node(6).

Node(6) is also not null, hence we move down the left subtree which is null. Null subtree returns 0. It is same for right subtree of node(6). So, node(6) return max(0,0) + 1 = 1 to parent node.

Back at node(7), there is right subtree too, so move down it to node(9).

As node(9) is not null, move down the left child which is node(8).

We move left of node(8) which is null and even right subtree is null, as all leaf node, it also return 1 to parent node.

 

At node(9), right child is null which return 0. So what should be height of node(9)? It will be max(1,0) + 1 = 2. 1 is height of left subtree and 0 is height of right subtree.
In the same vein, node(7) will return 3 to node(5).

At node(5), return max(1,3) +1 = 4.

 

Now, at node(10), we have height of left subtree let’s calculate height of right subtree. Move down to node(14).

 

Node(14) not null, move to left subtree to node(12).

 

As node(12) is not null, move to left side, which being null, return 0. Similarly for right child, it also returns 0. So, node(12) return max(0,0) +1 to parent node.

Move down to right subtree of node(14) to node(15).

As explained other cases, node(15) too will return 1.

At this point, we have height of left subtree and right subtree of node(14), hence return height  = max(1,1) + 1 = 2 to parent node.

Here, at node(10), we have height of left and right subtrees. What will be height of the binary tree then? it will be max(4,2) + 1 = 5.

Hope this example clarifies how recursive bottom up approach works to find height of binary tree.

Height of 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 MAX(a,b)  (a < b ? b : a)

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) return createNode(value);
        
    if (node->value > value)
        node->left = addNode(node->left, value);
    else
        node->right = addNode(node->right, value);
		
    return node;
}

int height( Node *root){
    if( !root ) return 0;
    
    int lheight = height( root->left);
    int rheight = height( root->right);
	
    return 1 + MAX (lheight, rheight );
}

/* Driver program for the function written above */
int main(){
    Node *root = NULL;
	
    //Creating a binary tree
    root = addNode(root, 30);
    root = addNode(root, 20);
    root = addNode(root, 15);
    root = addNode(root, 25);
    root = addNode(root, 40);
    root = addNode(root, 38);
    root = addNode(root, 39);
    root = addNode(root, 45);
    
    printf( "Height of tree is : %d", height( root));
    
    return 0;
}

Complexity of recursive method is O(n) as we will b scanning all nodes at least once. Be aware of drawback of recursive nature of this implementation as it may lead of stack overflow in production environments.

Two important things we learn from this problem : First how to traverse a tree which is part of solution to many of binary tree problems. Second, how to return values for subtrees to root and process those values at root node. We saw same thing happening in Replace node with sum of children in BST.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us at communications@algorithmsandme.com

Balanced binary tree

Balanced binary tree

What is a balanced binary tree?  A tree is balanced when difference between height of left subtree and right subtree at every node is not more than one. Problem is to check if given binary tree is balanced tree? For example, below tree is balanced tree because at all nodes difference between height of left and right subtree is not more than 1.

balanced binary tree

However, below tree is not balanced as difference between height of left subtree and right subtree at node(10) is 2.

Balanced binary tree : Thoughts

One thing to notice very carefully, that for a tree to be balanced, every subtree at each node should be balanced too. It cannot be balanced if it is balanced at root node.

As solution to original tree depends on subtree, we have to find first if subtrees are balanced. If yes, then compare the height of left subtree and right subtree, if difference is less than or equal to 1, return true. Refer Height of binary tree to learn how to find height of binary tree.

Let’s see how does it work with an example. Given below binary tree and see how we can figure out if it is balanced or not?

Start with root node which is node(10). Height of left subtree is 4 and right subtree is 3. Difference of heights is 1, now we have to check if it’s left and right subtrees are balanced?

At node(5), again height difference is 1, so we will go down left and right subtrees and check if they are balanced.

At node(1), it’s leaf node and hence, it must be balanced. So we return true to parent node(5).

Now, we have to check if right subtree of node(5) is balanced too? We move down right subtree and go all the way to node(6), which is leaf node, which returns true to node(8). Also, node(9) will return true. At node(8), both left and right subtree have returned true, we should return true from node(8) too.

At node(5), left and subtree have returned true and we know that difference between height of left and right subtree is only 1. Hence we will return true from node(5) too.

Next, we have to check if right subtree of node(10) is balanced too.

Left and right subtree of node(19) are leaf nodes, hence both will return true.

At node(19), left and right subtree has returned true and height difference is zero, hence it will return true to parent node.

Now, at last, we have received that left and right subtrees are balanced at node(10) and height difference is 1, hence, entire tree is balanced.

Balanced 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
#define MAX(a,b)  (a < b ? b : a)

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)
		return createNode(value);
    
	if (node->value > value)
		node->left = addNode(node->left, value);
	else
		node->right = addNode(node->right, value);
		
	return node;
}

int height( Node *root){
	if( !root ) 
		return 0;
	
	int lheight = height( root->left);
	int rheight = height( root->right);
	
	return 1 + MAX (lheight, rheight );
}

int isHeightBalanced( Node * root ){
	if(!root) return true;
	
	int lheight = height( root->left );
	int rheight = height( root->right );
	
	return (abs( lheight-rheight) <= 1 )
		   && isHeightBalanced( root->left )
		   && isHeightBalanced( root->right );
	
}
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
    
	//Creating a binary tree
	root = addNode(root, 30);
	root = addNode(root, 20);
	root = addNode(root, 15);
	root = addNode(root, 25);
	root = addNode(root, 40);
	root = addNode(root, 38);
	root = addNode(root, 39);
	root = addNode(root, 45);
	root = addNode(root, 47);
	root = addNode(root, 49);
    
	printf( "Is tree height balanced : %s", 
		isHeightBalanced( root ) ? "Yes" : "No" );
	
	return 0;
}

Complexity of algorithm to find if tree is balanced or not is O(n) as we will be scanning all nodes at least once. However, if you notice that we are scanning tree multiple times when calculating height of left and subtree at every node. How can we avoid these repeated scans?

As we are already scanning all nodes, can we pass the two things from subtree to root node? If we can pass from subtree if subtree is balanced or not and then what is height of subtree. Idea is to bump height all the way to root node and use that height to check if tree at root is balanced or not.

#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
#define MAX(a,b)  (a < b ? b : a)

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)
		return createNode(value);
    
	if (node->value > value)
		node->left = addNode(node->left, value);
	else
		node->right = addNode(node->right, value);
		
	return node;
}

int isHeightBalanced( Node * root, int *height ){
	if(!root){
		*height = 0;
		return true;	
	} 
	
	int lheight = 0, rheight = 0;
	int lBalanced = isHeightBalanced( root->left, &lheight );
	int rBalanced = isHeightBalanced( root->right, & rheight );
	
	//Update the height
	*height = 1 + MAX ( lheight, rheight);
	
	//Check if difference between two height is more than 1
	if (abs( lheight-rheight) > 1 ) return false;
	
	return lBalanced && rBalanced;
		  
}
/* Driver program for the function written above */
int main(){
	Node *root = NULL;
    
	//Creating a binary tree
	root = addNode(root, 30);
	root = addNode(root, 20);
	root = addNode(root, 15);
	root = addNode(root, 25);
	root = addNode(root, 40);
	root = addNode(root, 38);
	root = addNode(root, 39);
	root = addNode(root, 45);
	root = addNode(root, 47);
	root = addNode(root, 49);
    
	printf( "Is tree height balanced : %s", 
		isHeightBalanced( root ) ? "Yes" : "No" );
	
	return 0;
}

Complexity of this implementation is also O(n) however, number of scans of each node is only once.

Please share if there is something is wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com

Replace node with sum of children in BST

Replace node with sum of children

In last two posts : Delete binary search tree and Mirror binary search tree, we discussed how we can solve many problems using just traversal of tree. Next in the series is to replace node with sum of children in binary search tree.  For example, given below tree,

replace node with sum of children in binary search tree

output will be like

replace node with sum of children in BST

 

Replace node with sum of children : Thoughts

What do we need at the root node of the given tree. It is sum of all the nodes on left subtree and all the nodes on right subtree. At this point it is clear that left and right subtree should be processed before root node is updated. This is typical postorder traversal.
One more thing to note is that to solve problem at the root, we have to first solve the problem at left and right subtree level. This is makes implementation recursive.

One important question is what should happen at the leaf nodes. There are no children, hence no sum there. One of the assumption is to keep leaf nodes as is. However, I would recommend to bring this up with interviewer before coding the solution.

What will be the process step in postorder here? Once we have sum of left subtree and right subtree, all we have to do is to update root node value to sum of both.

I would strongly recommend to shut the browser and wok out an example to understand what needs to be done and how flow works.

OK, as you are done, can we do it together. Take tree as below, and we have to replace each node of this tree with sum of children.

replace node with sum of children in binary search tree

As always, we will start with root node. Node(10) has left and right subtrees, so we will find sum of those subtrees and add it to root node and replace root node with that number. We move down to left child node(5).

At node(5), again we have left and right subtree.  Move down to left child node(1).

As node(1) is leaf node without children, we will do nothing and go back to parent node(5), return 1 to parent node.

replace node with sum of children

Back at node(5), it has right subtree, hence move to node(6).

Node(6) is leaf node, move up to parent and return 6, value of the node itself.

replace node with sum in BST

At this point, we have sum of left and right subtree of node(5). Add them both along with value at root and replace the value of node(5). Here value at node(5) becomes 12. (5+6+1)

Left subtree is processed, move up the parent node(10). Since, node(10) has right subtree, go down the right subtree.

Node(19) has left subtree, so process the left subtree first.

replace node with sum of children i binary search tree

Node(17) is leaf node, no processing, return the node value to parent node.

Back at node(19), move down to node(21).

Since, node(21) is leaf node, we should return the root value to parent node.

At this point, left and right subtrees of node(19) are already processed. So add them with root value and replace root value with result. In this case its 57. (19 + 17 + 21 ).

Finally at node(10), left and right subtrees are processed, so add sum of left and right subtree with node value, and replace node value with result. In this case it is 79.

Replace node with sum of children : Implementation

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};
typedef struct node Node;

int replaceNodeWithSumOfChildren(Node *root){
	if (!root)
		return 0;
	int leftSum =  replaceNodeWithSumOfChildren(root->left);
	int rightSum = replaceNodeWithSumOfChildren(root->right);
	
	if(leftSum + rightSum != 0){
		root->value = leftSum + rightSum;
	}
	return root->value;
}

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){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	replaceNodeWithSumOfChildren(root);

	inoderTraversal(root);	
	return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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;
    }

    public void inorderTraversal(){
        inorder(this.root);
    }

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

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

    public void replaceWithSumOfChildren(){
        replaceWithSumOfChildrenRecursive(this.root);
    }

    private int replaceWithSumOfChildrenRecursive(Node root){
        if(root == null) return 0;

        boolean isLeaf = ( root.left == null && root.right == null);

        if(isLeaf) return root.value;

        //process left subtree
        int leftSum = replaceWithSumOfChildrenRecursive(root.left);
        //process right subtree
        int rightSum = replaceWithSumOfChildrenRecursive(root.right);

        root.value += leftSum + rightSum;

        return root.value;
    }
}

Test class

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.replaceWithSumOfChildren();
        binarySearchTree.inorderTraversal();
    }
}

Complexity of recursive way to replace node with sum of children is O(n) as we will be visiting each node at least once.

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 communications@algorithmsandme.com

Mirror binary search tree

Mirror binary search tree

In last post Delete binary search tree , we learned how to use traversals to solve problems on binary tree. Mirror binary search tree is another such problem which can be solved purely with one of the traversals of binary tree. What does it mean to mirror a binary tree?  It means to swap left and right subtree, left child of node becomes right child and right child becomes left child. This happens at every level. For example, for below binary tree,

mirror tree will be as below

Mirror binary search tree : Thoughts

As we can see that to mirror a tree, we have to first mirror it’s left and right subtree.  Mirror process will be same for subtrees will also be the same, hence perfect case for recursive implementation.

Idea is to start from root node, check if there are left and right child. If no, do nothing. If yes, then move down the left child and first mirror the left subtree. Then if there is right child, mirror the right subtree and then finally swap left and right child of the node. This is typical postorder processing, where left and right subtrees are processed before root node. Processing here is to swap left and right child of node.

When do we stop? When node is leaf node, with node left and right child.

Mirror binary search 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;

void mirrorBST(Node * root){
	if(!root)
		return;
	
	mirrorBST(root->left);
	mirrorBST(root->right);
	
	Node * temp  = root->right;
	root->right  = root->left ;
	root->left   = temp;
}

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){
	if(node == NULL){
		return createNode(value);
	}
	else{
		if (node->value > value){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	mirrorBST(root);

	inoderTraversal(root);	
	return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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;
    }

    public void mirror(){
        mirrorRecusrive(this.root);
    }
    private void mirrorRecusrive(Node root){
        if(root == null) return;

        //mirror left subtree
        mirrorRecusrive(root.left);
        //mirror right subtree
        mirrorRecusrive(root.right);

        //swap left and right child
        Node temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

Test class

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.mirror();
        binarySearchTree.inorderTraversal();
    }
}

Mirror binary search tree : example

Let’s take an example and see how function works. Below is the tree to mirror.

We start with node(10). As it has left and right subtree, we have to first mirror those subtrees before we can swap left and right child of node(10).

Move down to left subtree to node(5), problem is reduced to mirror tree rooted at node(5).

As node(5) has left child, move down to left child which is node(1).

This the special case, as node(1) is leaf node, there is no need to swap anything. It also means tree rooted at node(1) is already mirrored. We move up the tree at node(5). As it has right child, we move down the right subtree at node(6).

Again, node(6) is leaf node so subtree at node(6) is already mirrored.

At this point, left and right subtrees of node(5) are mirrored, so just swap left and right child.

Now, tree rooted at node(5) is mirrored. We move up the root which is node(10).

Since, node(10) has right subtree, we have to first mirror right subtree.

Again, node(19) has left and right subtrees, we move down the left subtree.

Node(17) is leaf node, it is already mirrored.

Move down the right subtree to node(21). It is leaf node hence, already mirrored.

Now, we have mirrored both left and right subtree, all we need to swap left and right child.

At node(10), both it’s subtrees are mirrored, swap left and right child.

Complexity of algorithm to mirror binary search tree is O(n) as we have to scan all nodes at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us at communications@algorithmsandme.com.

Delete binary search tree

Delete binary search tree

In last post Binary search tree traversals we discussed various kind of traversals of tree like inorder, preorder and post order traversals. One of the many problems which can be solved using these traversals is to delete binary search tree. Problem is : given a binary search tree, delete all nodes of it.

Delete binary tree : Thoughts

As always, we would start from the root of the binary tree. What choice do we have here? We can delete the root node immediately. We can delete left subtree first and then delete root node. Or we can delete left subtree, right subtree and then delete the node.
If we delete root node immediately, we lose access to left and right subtree as root node contains references to these. Deletion of root upfront would have been preorder traversal.

If we delete root node after deleting left subtree, we lose reference to right subtree. So, we can not delete root node before deleting both left and right subtree. That means we will be processing root node last. What kind of traversal is that? Of course postorder traversal, instead of print node, delete node.

Recursive nature of problem is evident that to delete a tree, we have to first delete the subtree and then it’s subtree and so on.

Delete binary search 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;

void deleteBST(Node *root){
	if(!root)
		return ;
	
	//Process left subtree
	deleteBST(root->left);
	//Process right subtree
	deleteBST(root->right);
	//Free the root node
        root->left = NULL;
        root->right = NULL;
	free(root);
}

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){
			node->left = addNode(node->left, value);
		}
		else{
			node->right = addNode(node->right, value);
		}
	}
	return node;
}

/* Driver program for the function written above */
int main(){
	Node *root = NULL;
	//Creating a binary tree
	root = addNode(root,30);
	root = addNode(root,20);
	root = addNode(root,15);
	root = addNode(root,25);
	root = addNode(root,40);
	root = addNode(root,37);
	root = addNode(root,45);
	
	deleteBST(root);
	
	return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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;
    }

    public void delete(){
        deleteRecusrive(this.root);
        this.root = null;
    }
    private void deleteRecusrive(Node root){
        if(root == null) return;

        //delete left subtree
        deleteRecusrive(root.left);
        //delete right subtree
        deleteRecusrive(root.right);

        //delete the root, which will be collected by GC
        root.left = null;
        root.right = null;
    }
}

Test class

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.delete();
        binarySearchTree.inorderTraversal();
    }
}

Delete binary search tree : Example

Let’s see how it works. Given below binary search tree, we have to delete it.

We start with node(10), can we delete it? No we cannot because there is left subtree and right subtree attached to it.


Move down the node(5), and check if it can be deleted. No as  it has left and right child.

delete binary search tree

Again, we move down to left subtree, and new candidate for deletion is node(1). Can we delete it? Yes as it is leaf node with no left or right child.

delete binary tree

After deleting node(1), we move back to it’s parent node(5), we cannot still delete node(5) as there is right subtree to it.

delete a bst

We move down the right subtree, which is node(6). Can we delete it? Yes we can as it’s a leaf node.

delete a binary search tree

Once, we delete node(6), new candidate for deletion is again node(5).  Can we delete node(5) now? Yes as we already deleted left and right subtree of the node, we can safely delete it.

delete binary search tree

After deleting node(5), we move up to it’s parent which is node(10). Can we delete it? No as there is right subtree to it.

Our new candidate for deletion is node(19), can we delete it? Nope, as it has left and right subtree to it.

Move down the left subtree and candidate is node(17).

Delete node(17) and move up to the parent node(19), however, do not delete node(19) still as there is right child of it.

Now, move down to node(21).

Delete node(21) as it is leaf node. After deleting node(21), we move up to parent which is node(19).

Can node(19) be delete now? Yes as left and right subtree have been deleted, parent node can be deleted safely.

Same as other nodes, delete node(10) too.

Complexity of algorithm to delete binary search tree is O(n) as we scan all the nodes of tree at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across world, please reach out to us on communications@algorithmsandme.com

Binary search tree traversals

Binary search tree traversals

Most of the problems on binary search tree can be solved using one or other traversal of tree. There are three types of binary search tree traversals : Preorder traversal, Inorder traversal and Postorder traversal. Let’s discuss each one in detail.

Preorder traversal of BST

Preorder traversal means traverse the root node first, then left subtree and at last traverse right subtree. For example, given below tree, preorder traversal will be 10,5,1,,6,19,17,21.

binary search tree traversals

As we already know that binary search tree is recursive data structure, any traversal can be solved recursively. Start with the root, then do a preorder traversal of left subtree and then at last do the preorder traversal of right subtree.

In above example,  after traversing root node(10), left subtree is traversed in preorder [5,1,6]. Same is true after traversing node(5).

Preorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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);
    }
}

Inorder traversal of BST

Inorder traversal means traverse left subtree first, then root node and at last traverse right subtree. For example, given below tree, inorder traversal will be 1,5,6,10,17,19,21.

preorder travesal binary search tree

Again following the recursive strategy, if node has left child, do inorder traversal on left subtree, once inorder traversal of left subtree is done, visit root node and then again do inorder traversal of right subtree.

In above example,  before traversing root node(10), left subtree is traversed in inorder [1,5,6]. Same is true before traversing node(5).

Inorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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);
    }
}

Postorder traversal of BST

Postorder traversal means traverse left subtree first, then right subtree and at last visit root node. For example, given below tree, postorder traversal will be 1,6,5,17,21,19,10.

postorder traversal of binary search tree

Again following the recursive strategy, if node has left child, do postorder traversal on left subtree, then do postorder traversal of right subtree and finally visit root node.

In above example,  before traversing root node(10), left subtree is traversed in postorder [1,6,5] and then right subtree is traversed in postorder [17,21,19] and then finally node(10).

Postorder traversal implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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 preOrder(Node root){
        if(root == null) return;

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

In next few posts, we will discuss problems which can be solved using these traversals.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com

Path with given sum in binary search tree

Path with given sum in binary search tree

In last post Paths in Binary Search Tree we discussed and solved problem to find all the paths in binary search tree. Next step is to find specific path with sum in binary search tree. Given a number K, find all paths with sum K in BST. For example if K  = 21, and given below BST, path will be [10,5,6].

path with given sum in binary search tree

Keep in mind, that there can be more than one paths with given sum. Confirm with interviewer what does he expects in implementation.

Path with given sum : Thoughts

We already know how to traverse all paths in binary search tree. All we need now is to qualify those paths if all nodes in path sum up to given number K.

Let’s figure our recursive nature of problem. At the root level, we are required to find path with sum K. As soon as we add root in path, remaining nodes in path needs to add up to K – root.value, in either left or right subtree. For example, in below tree,  at whole tree level, sum required is 21.

As we move down, that is root is added to path, sum required further is 11 from either left or right subtree. Problem is reduced to subproblem.

At this point, we cannot go forward with node(19), as sum required will reduced to negative. However, we can move down node(5) and problem is reduced to finding path with sum 6.

path with given sum

At this point, we have to find path with sum 6 in left and right subtree of node(5). On left subtree, add node(1) to path. Now problem reduces to finding path with sum 5 on right and left subtree of node(1). However, there are not subtrees of node(1). Hence, path [ 10,5,1 ] is not correct path.

On the other hand, after adding node(6) in path, sum required is 0 and also node(6) is a leaf node, hence path [10,5,6] is required path with given sum in binary search tree.

As we worked out example, we came up with some basic conditions for algorithm.

  1. If at any node in path, sum required becomes negative, do not go down the path.
  2. If sum required become zero, check if the last node added is leaf node. If yes, then add path to solution.
  3. If sum required is greater than zero, and node is leaf node, then that path is not with required sum.

Paths with given sum  : Implementation

#include<stdio.h>
#include<stdlib.h>
 
struct node{
	int value;
	struct node *left;
	struct node *right;
};

typedef struct node Node;

void printPath(Node * node, int sum, int path[], int pathLen){
	
	if(!node)
		return;
	
	int subSum = sum - node->value;
	path[pathLen] = node->value;
	
	int isLeaf = !( node->left || node->right );
        if(isLeaf && subSum == 0){
        	printf(" Path with given sum is: " );
	        for(int i=0; i<=pathLen; i++)
               	     printf("%d, ", path[i]);
           	printf("\n");
        }  
        printPath(node->left, subSum, path, pathLen+1);
        printPath(node->right, subSum, path, pathLen+1);
        return ;
}

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){
        node->left = addNode(node->left, value);
      }
      else{
        node->right = addNode(node->right, value);
      }
  }
  return node;
}
 
/* Driver program for the function written above */
int main(){
  Node *root = NULL;
  int n = 0;
  //Creating a binary tree
  root = addNode(root,30);
  root = addNode(root,20);
  root = addNode(root,15);
  root = addNode(root,25);
  root = addNode(root,40);
  root = addNode(root,37);
  root = addNode(root,45);
  int path[100];
  printPath(root, 115, path, 0);
  
  return 0;
}

Java implementation

package com.company.BST;

import java.util.ArrayList;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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 pathWithGivenPath(Node root, int sum, ArrayList<Node> path){
        if(root == null)
            return;

        if(sum < 0) return;

        int subSum = sum - root.value;
        path.add(root);

        boolean isLeaf = ( root.left == null && root.right == null );
        if(isLeaf && subSum == 0){
            path.forEach(node -> System.out.print(" " + node.value));
            System.out.println();
        }
        pathWithGivenPath(root.left, subSum, path);
        pathWithGivenPath(root.right, subSum, path);

        path.remove(path.size()-1);
    }

    public void printPathWithGivenPath(int sum){
        ArrayList<Node> path = new ArrayList<>();
        pathWithGivenPath(this.root, sum, path);
    }
}

Test class

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.printPathWithGivenPath(20);
    }
}

Complexity of algorithm to print all paths with given sum in binary search tree is O(n) as we will be scanning all nodes of BST at least once.

Please share if there is something wrong or missing. If you want to contribute and share your knowledge with thousands of learners across the world, please reach out to us at communications@algorithmsandme.com

Search in Binary Search Tree

Search in Binary Search Tree

In previous post Binary Search Tree : Insertion we discussed basics about binary search tree and learned how to insert a node in BST.  One thing binary search tree data structure is known for is fast search.  Let’s discuss how to search in binary search tree? Given an key and BST, check if key exists in BST or not. For example :In below tree, if searched key is 6, answer is True and if searched key is 8, answer should be False.

search in binary search tree

What is brute force solution for search? We go through all nodes of tree and check if the value of node is what we are looking for. If yes, then return True. If we scanned all nodes and no node has key, returned false. Complexity of this search will O(n) where n is number of nodes in BST.

Search in binary search tree : Line of thought

Can we do better than linear complexity?  In brute force approach, we did not use binary search tree property that all nodes in left subtree are less than root and all nodes in right subtree are greater than root. If value in root node is greater than value being searched, what does it tell about other nodes? If value in root node is greater than key, we can guarantee that all nodes on the right subtree will be less than searched value.
What if value at root node is less than key? In that case we know all nodes on left subtree must be less than searched value.

In any case, we can discard either left or right subtree and look for element in other subtree. Sounds familiar to Binary search algorithm ?

In binary search algorithm, we can again split the remaining subarray into half, can we do in BST? Of course. Since all nodes follow the BST property, we can always split on each node, discarding one subtree and search in other based on relationship between value in value of root node and searched value. This gives us hint about recursive implementation.

If value at root is equal to searched value, return true. If we find root node as null, there is no such key in tree.

Search in binary search tree : Algorithm

  1. While there is a node in binary search tree
    • If root.value ==  key return true
    • If root.value > key, search in left subtree, root = root.left, go to step 1.
    • If root.value < key, search in right subtree, root = root.right, go to step 1.
  2. If there is no node in tree, return false.

Let’s take an example and see how this algorithm works? Given below BST, find key 6.

search in binary search tree

First of all, there are nodes in BST, hence check if root.value is equal to key? In this case (10) is greater than (6). So all nodes on right subtree of node(10) will be greater than (6), hence discard right subtree and focus on left subtree.

Now, the root node of left subtree is node(5). There are nodes in tree hence, check if root.value is equal to key. Here, (5) is less than key(6), so all nodes on left subtree will be less than key(6). Discard left subtree and focus on right subtree of node(5).

There are nodes in subtree, so check again root.value == key. Now root.value is equal to key, return true.

Can you find the flow to find key 9 in the same tree?

Search in binary search tree : Recursive implementation

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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 boolean searchRecursive(Node root, int value){
        if(root == null) return false;

        if(root.value == value) return true;
        if(root.value > value ) return searchRecursive(root.left, value);
        if(root.value < value ) return searchRecursive(root.right, value);

        return false;
    }

    public boolean search(int value){
        return this.searchRecursive(this.root, value);
    }
}

Test code

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);

        boolean isFound = binarySearchTree.search(15);
        System.out.print( isFound ? "Element found" : "Element not found");

    }
}

Complexity of search in binary search is very tricky question.  It’s common mistake to think that worst case complexity of search in BST is O(log n) same as binary search algorithm. However, this is true only when BST is balanced tree and at every node, we can discard half of the nodes. What is all nodes of tree are on one subtree only as show below. In that case worst complexity of search will be O(n).

Please share if there is something wrong or missing. If you want to share your knowledge with thousands of learners across the world, please reach out to us on communication@algorithmsandme.com

 

Insertion in Binary Search Tree

Insertion in Binary Search Tree

Binary search tree is a data structure consisting of nodes, each node contain three information : value of the node, pointer or reference to left subtree and pointer or reference to right subtree. Property that distinguishes binary search tree from binary tree is that the data of all the nodes in the left sub-tree of the root node should be less than the data of the root and data in right subtree of the root node should be greater than or equal to data of the root. In today’s post we will see insertion in binary search tree.

binary search tree

For example :  Root node is with data = 10, data in the left subtree is: [5,1,6]; All data elements are < 10; Data in the right subtree is: [19,17,20].All data elements are > 10

Notice that property that data of all nodes on left subtree should be less and data on all in right subtree should be greater than root is followed at every node. So, for each node, it’s left subtree and right subtree are also binary search tree. This property helps to solve almost all problems on binary search tree recursively.

How to declare a node of a binary search tree?

    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;
        }
    }

Insertion in binary search tree

The structure and placement of each node depends on the order it is inserted into binary search tree. However, every insertion should leave binary search tree in correct state.  A new node is added to binary search tree based on value.

If the node is very first node to added to BST, create the node and make it root. However,if there are already existing nodes in BST,  follow the below steps :

  1. If value of current node is greater than value of new node, insert node in left subtree. If left child of current node is null,  attach new node as left child of current node. Else, move down the left child, now current node is left child.
  2. If value of current node is less than value  to  insert, insert node in right subtree. If right child of current node is null, attach new node as right child. Else, move down the right child. Right child become current node.

If you notice, above algorithm can be implemented recursively. At every node, problem reduces to subproblem which is to insert node in either left or right subtree depending on the relationship between value in current node and value to insert.

Let’s see an example and learn how to insert a node in BST.  Tree is given below and say we have to insert 8.

binary search tree

Check root, it is greater than value to insert, so node(8) will be on left subtree of root.

insert in binary search tree

Since left child is not null, left child will become current node, which is node(5).

5 is less than value to be inserted, hence 8 will be on the right subtree of node(5).  However, right child of node(5) is not null, hence right child(6) will become current node.

insert into binary search tree

At this point, node(6) is less than value (8), which means, node will be added to right subtree. As right child of node(6) is null, new node will be right child of it.

Final binary search tree will look like this.

insert in bst

Insert node in binary search tree : Recursive implementation

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    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;
    }
}

Test class

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.inorderTraversal();

    }
}

What is complexity to insert a node in binary search tree?  At every node, we split the tree into two and discard the half of the tree. So recurrence relation is T(n) = T(n/2) + 1 which gives complexity to be O(log n). However, there is big assumption in here, which is binary search tree is balanced and there almost equal nodes on both side of each node, which may or may not be the case. In worst case, all nodes on BST are on one side of root node. When a new node is inserted, in worst case, we will scan all n nodes of tree. Hence, worst case complexity to insert a node in binary search tree is O(n).

There is another problem which comes with any recursive solution : danger of stack overflow. As number of nodes grow in binary search tree and if tree gets skewed, we may end up with n stack frames on stack.  In production, this n can be in millions and even billions. Depending of the size of each stack frame, we may run out of stack frames sooner or later. To get the gravity of problem of skewed binary search tree understand that for 1 billion nodes, in balanced BST, only 9 stack frames will be required where as for completely skewed BST, 1 billion stack frames will be required.

Insert in binary search tree : Iterative implementation

public void insertIterative(int value){
        if(this.root == null){
            this.root  = new Node(value);
        }
        else{
            Node currentNode = root;
            Node parent = null;
            while(currentNode != null){
                parent = currentNode;
                if(currentNode.value > value) {
                    currentNode = currentNode.left;
                }
                else{
                    currentNode = currentNode.right;
                }
            }

            //Parent cannot be null here
            if(parent.value > value){
                parent.left = new Node(value);
            }
            else {
                parent.right = new Node(value);
            }
        }
    }

How do you know that your insertion is correct? Best way is to traverse the tree in inorder way. In Inorder traversal we visit left subtree of node first before visiting root node and in last visit right subtree. This traversal should give nodes of tree in sorted order. If that’s the case, insertion function is working fine.

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

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

Complexity of inorder traversal of BST is O(n) as we visit every one at least once. Above implementation is recursive, in future posts, we will be working on iterative implementation of all traversals of binary search tree.

Please share if there is something wrong or missing. We would be glad o hear from you in comments, mails or any other channel. If you are willing to share you knowledge and help thousands of learners across world, please reach out to us on communications@algorithmsandme.com