# Print paths in binary search tree

Print paths in binary search tree from root to leaf node. There can be many paths in a tree. AT every node, there are two paths splitting. Maximum length of path in binary search tree can be N nodes. Consider following tree: Paths in given binary search tree are : [ 10,5,1 ], [10,5,6 ], [10,19,17 ], [10,19,20]

## Paths in binary search tree : Algorithm

As every path start with root node, it’s obvious that first node in every path with root node.  At root node, we have two choices. We can go to left subtree or can go to right subtree. It does not matter what subtree we go first as we have to traverse all paths anyway.

Let’s say we traverse left subtree first. At this point, we have first node in path, all we need to find all paths in left subtree and append those path with first node we have.
At first left child, problem remains the same, find paths in binary search tree. Additional step is to append to existing path we have already have covered. Are you getting a hint on recursive nature of problem?

Once, we have traversed all paths on left subtree, it’s time to traverse all paths on right subtree.

To keep track of nodes which are already added to path, we have to maintain a list of nodes, which will be updated whenever we move up and down in BST.

As mentioned, path ends on leaf node, as soon as we hit a node which has no left or right child, start going back up in the tree. In implementation terms, this will be termination condition for recursive function. Algorithm to print paths in binary tree.

### Paths in binary search tree : Implementation

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

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

typedef struct node Node;

void printPaths(Node * node, int path[], int pathLen){

int i;

if(!node)
return;

path[pathLen]  = node->value;

int isLeaf = ! ( node->left || node->right ) ;
if(isLeaf ){
printf("\n Path till node %d is :", node->value);
for(i=0; i<=pathLen; i++){
printf("%d, ", path[i]);
}
}

printPaths(node->left,  path, pathLen+1);
printPaths(node->right, 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){
}
else{
}
}
return node;
}

/* Driver program for the function written above */
int main(){
Node *root = NULL;
int n = 0;
//Creating a binary tree
int path;
printPaths(root, 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;
}

public void printPath(){
ArrayList<Node> path  = new ArrayList<>();
this.printPathRecursive(this.root, path);
}

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

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

printPathRecursive(root.left,path);
printPathRecursive(root.right, path);

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

}
}
```

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.printPath();
}
}
```

Since we are traversing each node at least once, complexity of  implementation for print all paths in binary search tree is  O(n) where n is number of nodes.

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 [email protected]

Posted on Categories Binary Search Tree, Data Structures1 Comment on Paths in Binary Search Tree

## Check if tree is BST or not

This is one of the most asked programming interview questions. How to check or validate that a given binary tree is BST or not or if a given tree is a binary search tree? For example, the first and second binary trees are BST but not the third one.

In binary tree introduction  we touched upon the topic of recursive structure of binary search tree.  The first property to satisfy to be qualified as BST is: value in all nodes on the left subtree of the root node are smaller and the value of all nodes in the right subtree is greater than the root node. This property should be valid at all nodes.

## Check if binary tree is (BST) or not: Recursive implementation

So, to see if the binary tree rooted a particular node is BST, the root is greater than all nodes on the left subtree and less than all nodes on the right subtree. However, is it sufficient condition? Let’s take a counterexample and prove that even root is greater than all nodes on the left side and smaller than all nodes on the right subtree, a binary tree may not be binary search tree. Look at the tree below. In this tree above condition is satisfied, but we cannot call this binary tree a BST.

This is a recursive structure of a binary search tree that plays an important role. For a binary tree root at a node to be BST, it’s left subtree and right subtree should also be BST. So, there are three conditions which should be satisfied:

1. Left subtree is BST
2. Right subtree is BST
3. Value of root node is greater than the max in the left subtree and less than minimum in right subtree

### Check if binary tree is (BST) or not  : Recursive implementation

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

#define true 1
#define false 0

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

typedef struct node Node;

Node * findMaximum(Node * root){
if( !root ) return root;
while( root->right ){
root = root->right;
}
return root;
}

Node * findMinimum(Node * root){
if( !root ) return root;
while( root->left ){
root = root->left;
}
return root;
}

int isBST(Node * node){

if(!node)
return true;

if( ! ( node->left || node->right ) ) return true;
int isLeft  = isBST(node->left);
int isRight = isBST(node->right);

if(isLeft && isRight){
/* Since we already know that left sub tree and
right sub tree are Binary search tree, finding min and max in them would be easy */

Node *max  =  NULL;
Node *min  =  NULL;
if( node->left )
max = findMaximum(node->left);
if( node->right )
min = findMinimum(node->right);

//Case 1 : only left sub tree is there
if(max && !min)
return node->value > max->value;
//Case 2 : Only right sub tree is there
if(!max && min)
return node->value < min->value;
//Case 3 : Both left and right sub tree are there
return (node->value > max->value && node->value < min->value);
}
return false;
}

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;
//Creating a binary tree

printf("%s", isBST(root ) ? "Yes" : "No" );

return 0;
}
```

#### Check if binary tree is (BST) or not  : Optimized implementation

Above implementation to check if the binary tree is binary search tree or not is correct but inefficient because, for every node,  its left and right subtree are scanned to find min and max. It makes implementation non-linear.

How can we avoid re-scanning of left and right subtrees? If we can keep track max on left subtree and min on right subtree while checking those subtrees for BST property and use the same min and max.

Start with INTEGER_MAX and INTEGER_MIN, check if the root node is greater than max and less than min. If yes, then go down left subtree with max changed to root value, and go down to right subtree with min changed to root value. It is a similar implementation as above, except revisiting nodes.

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

#define true 1
#define false 0
#define INT_MIN -32999
#define INT_MAX 32999

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

typedef struct node Node;

int isBSTHelper(Node *root, int max, int min){
if(!root) return true;

if(root->value < min || root->value > max){
return false;
}

return isBSTHelper(root->left, root->value, min) &&
isBSTHelper(root->right, max, root->value);
}

int isBST(Node *root){
return isBSTHelper(root, INT_MAX, INT_MIN);
}

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;
//Creating a binary tree

printf("%s", isBST(root ) ? "Yes" : "No" );

return 0;
}
```

The complexity of the above implementation is O(n) as we are traversing each node only once.

Another method to see if the binary tree is BST or not is to do an inorder traversal of the binary tree and keep track of the previous node. As we know in-order traversal of a binary search tree gives nodes in sorted order, previously visited node should be always smaller than the current node. If all nodes satisfy this property, a binary tree is a binary search tree. If this property is violated at any node, the tree is not a binary search tree.

The complexity of this implementation is also O(n) as we will be traversing each node only once

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

Posted on 3 Comments on Check if tree is BST or not

## Closest element in a binary search tree

The problem statement is: given a binary search tree and a value, find the closest element to that value in the binary search tree. For example, if below is the binary search tree and value given is 16, then the function should return 15.

### Closest element in BST: thoughts

A simple approach is to go to all nodes of BST and find out the difference between the given value and value of the node. Get the minimum absolute value and add that minimum value from the given value, we would get the closest element in the BST.

Do we really need to scan all the nodes? No we don’t need to. Let’s say given value is k.

What if current.value is equal to the k? That means it is the closest node to the k and we cannot go better than this. Return the node value as closest value.

If current.value is greater than k, by virtue of BST, we know that nodes on the right subtree of the current node would be greater than the current.value. Hence the difference between k and all the nodes on the right subtree would only increase. So, there is no node on the right side, which is closer than the current node itself. Hence, the right subtree is discarded. If there is no left subtree, return current.value.

If current.value is less than k,  with the same logic above, all elements in left subtree are less than the value of current.value, the difference between k and the nodes on left subtree would only increase. So, we can safely discard the left subtree. If there is no right subtree, return current.value.

When we return the closest element from left subtree, we check if the difference between current.value and k less than difference between returned value and k. If it is less, then return current.value else return the returned value from the subtree.

### Closest element in a binary search tree: algorithm

1. If `k == current.value`, return current.value.
2. If `k < current.value`, search the closest element in left subtree including the root as current is still a candidate.
1. Return current.value if there is no left subtree.
3. If `k > current.value`, search the closest element in the right subtree.
1. Return current.value if there is no right subtree.
4. If `abs(current.value - k ) < abs(returnedValue - k )`, return current.value else return returnedValue

#### Closest element in binary search tree: implementation

```package com.company.BST;

/**
* Created by sangar on 3.11.18.
*/
public class ClosestElement {

public int findClosest(TreeNode node, int k){
if(node == null) return -1;

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

if(currentValue == k) return currentValue;

if(currentValue > k){
if(node.getLeft() == null) return currentValue;

//Find closest on left subtree
int closest = findClosest(node.getLeft(), k);
if(Math.abs(closest - k) > Math.abs(currentValue - k)){
return currentValue;
}
return closest;
}
else {
if (node.getRight() == null) return currentValue;

//Find closest on right subtree
int closest = findClosest(node.getRight(), k);
if (Math.abs(closest - k)
> Math.abs(currentValue - k)) {
return currentValue;
}
return closest;
}
}
}
```
```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;
}
}

```
```package test;

import com.company.BST.BinarySearchTree;
import com.company.BST.ClosestElement;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class ClosestElementTest {

ClosestElement tester = new ClosestElement();

@Test
public void closestElementTest() {

BinarySearchTree<Integer> binarySearchTree =
new BinarySearchTree<>();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

assertEquals(6,
tester.findClosest(binarySearchTree.getRoot(),1));
}
}

```

Complexity of algorithm to find closest element in a binary search tree is O(n) if tree is completely skewed.

Posted on Categories Binary Search Tree, Data StructuresLeave a comment on Closest element in binary search tree

## Two nodes with a given sum in a binary search tree

Given a binary search tree and an integer k, find all two nodes with given sum, nodes (a,b) such that a+b =k. In other words, find two nodes in a binary search tree which add to a number. For example, in the binary search tree given below, if k = 24, node(5) and node(19) should be the result.

### Two nodes with given sum in binary search tree: thoughts

We have solved a similar problem with arrays, where we had to find pairs with a given sum k, the basic idea was that if the array is sorted, we will scan it from start(moving right) and end(moving left), and see if elements at two ends add up to k. If the sum of those numbers is greater than k, we move to right from start. If the sum of those two numbers is less than k, we move to left from end. We continue till two pointers cross each other.

Is there a way in which binary search tree can be sorted array? Yes, if BST is traversed in inorder, output is in sorted order of nodes. So, if we scan the BST and store in an array, the problem is same as find pairs in an array with a given sum.
However, the solution requires two scans of all nodes and additional space of O(n).

Another solution could be to use a hash map. Each node is stored in the hashmap and at each node, we check if there is a key (sum-node.value) present in the hashmap. If yes, then two nodes are added into the result set. This still requires additional space, however, there is only one traversal of the tree.

How can we avoid additional space? Look at the binary search tree property: all the nodes on the left subtree of a root node are less than and all the nodes on right subtree are greater than the root node.
We know that the minimum node in BST is the leftmost node and the maximum node is the rightmost node.
If we start an inorder traversal, the leftmost node is the first node to be visited and if we do a reverse inorder traversal, the rightmost node is the first node will be visited. If the sum of the minimum and the maximum is less than k, then we have to go to the second minimum (next node in forward inorder traversal). Similarly, if the sum of the minimum and the maximum is greater than k, then we have to go to the second maximum(next in reverse inorder traversal)

How can we do a forward and reverse inorder traversal at the same time?

### Sum of two nodes in binary search tree: stacks

We know how to traverse a tree using stack data structure. We will use two stacks, one stack stores the nodes to be visited in forward inorder traversal and second stores the nodes to be visited in reverse inorder traversal. When we reach the leftmost and the rightmost node, we pop from the stacks and check for equality with the given sum.
If the sum of the two nodes is less than k, we increase one of the nodes. We will go to the right subtree of the node popped from the forward inorder stack. Why? Because that’s where we will find the next greater element.

If the sum of the two nodes is greater than k, we decrease one of the nodes. We will go to the left subtree of the node popped from the reverse inorder stack. Why? Because that’s where we will find the next smaller element.

We will continue till both forward and reverse inorder traversal do not meet.

#### Two nodes with given sum in BST: Implementation

```package com.company;

import com.company.BST.TreeNode;
import javafx.util.Pair;

import java.util.ArrayList;
import java.util.Stack;

/**
* Created by sangar on 26.11.18.
*/
public class TwoNodesWithGivenSum {
public ArrayList<Pair<Integer, Integer>>
findPairsWithGivenSum(TreeNode root, int sum) {

Stack<TreeNode> s1 = new Stack<>();
Stack<TreeNode> s2 = new Stack<>();

ArrayList<Pair<Integer, Integer>> result
= new ArrayList<>();

TreeNode cur1 = root;
TreeNode cur2 = root;

while (!s1.isEmpty() || !s2.isEmpty() ||
cur1 != null || cur2 != null) {
if (cur1 != null || cur2 != null) {
if (cur1 != null) {
s1.push(cur1);
cur1 = cur1.getLeft();
}

if (cur2 != null) {
s2.push(cur2);
cur2 = cur2.getRight();
}
} else {
int val1 = (int)s1.peek().getValue();
int val2 = (int)s2.peek().getValue();

if (s1.peek() == s2.peek()) break;

if (val1 +  val2 == sum)

if (val1 + val2 < sum) {
cur1 = s1.pop();
cur1 = cur1.getRight();
} else {
cur2 = s2.pop();
cur2 = cur2.getLeft();
}
}
}

return result;
}
}

```

Test cases

```package test;

import com.company.BST.BinarySearchTree;
import com.company.TwoNodesWithGivenSum;
import javafx.util.Pair;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class TwoNodesWithGivenSumTest {

TwoNodesWithGivenSum tester = new TwoNodesWithGivenSum();

@Test
public void twoNodesWithGivenSumTest() {

BinarySearchTree<Integer> binarySearchTree
= new BinarySearchTree<>();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

ArrayList<Pair<Integer, Integer>> result
= new ArrayList<>();

assertEquals(result,
tester.findPairsWithGivenSum(
binarySearchTree.getRoot(),
27
)
);
}

@Test
public void twoNodesWithGivenSumNotPossibleTest() {

BinarySearchTree<Integer> binarySearchTree
= new BinarySearchTree<>();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

ArrayList<Pair<Integer, Integer>> result
= new ArrayList<>();
assertEquals(result,
tester.findPairsWithGivenSum(
binarySearchTree.getRoot(),
45
)
);
}

@Test
public void twoNodesWithGivenSumNullTreeTest() {

ArrayList<Pair<Integer,Integer>> result
= new ArrayList<>();

System.out.println(result);

assertEquals(result,
tester.findPairsWithGivenSum(
null,
45
)
);
}
}

```

The complexity of this method to find two nodes with a given sum in a binary search tree is O(n). We are storing nodes in stacks, which will have space complexity of O(n), however, it is less than the previous solutions as it actually making the recursive stack explicit.

Please share if you have any doubts or something is missing or wrong. If you are preparing for an interview, signup to receive a free interview kit.

Posted on Categories Binary Search Tree, Data StructuresLeave a comment on Two nodes with given sum in binary search tree

## Lowest common ancestor (LCA) in BST

Given a binary search tree and two nodes, find the lowest node which is the parent of both given nodes, that is the lowest common ancestor (LCA). For example, in the following tree, LCA of 6 and 1 is node(5), whereas the lowest common ancestor of nodes 17 and 6 would be a node(10). What is the condition for a node to be LCA of two nodes?  If paths for given nodes diverge from the node, then the node is the lowest common ancestor. While the path is common for both the nodes, nodes are common ancestor but they are not lowest or least. How can we find where paths are diverging?

Paths are diverging when one node is on the left subtree and another node is on the right subtree of the node. The brute force solution would be to find one node and then go up the tree and see at what parent node, other given node falls on the opposite subtree.

Implementation wise, traverse to node 1 and node 2, and store both paths on the stack. Then pop from two stacks till you find the same node on both paths, that node would be the lowest common ancestor. There will be two scans of the tree and additional space complexity to store paths which in the worst case be `O(n)`.

However, the brute force solution does not use the property of a binary search tree. Property is that all the nodes on the left side of a node are smaller and all the nodes on the right side of a node are greater than node. Can we use that property to solve this problem?

Basic idea is to return the node if it is found in any of the subtrees. At any node, search for both given nodes in the left subtree.  If we get a non-empty node returned from the left subtree, there is at least one of the two nodes is on the left subtree.

Again, search in right subtree these two nodes, if a non-empty node is returned from the right subtree, that means at least one of the nodes is on the right subtree.

What does it means if we have a non-empty node on both left and right subtree? It means two nodes are on the left and right subtree, one on each side. It means the root node is the lowest common ancestor.

What if one of the returned nodes is empty? It means both nodes are on one side of the root node, and we should return the upwards the non-empty node returned.

Let’s take an example and see how does it work? Given the below tree, find the lowest common ancestor of node(1) and node(9). Start with the node(10) and look for the left subtree for both node(1) and node(9). Go down all the way to the node(1), at the time, we return 1 as the node as node.value is equal to one of the nodes.  At node(5), we have got node(1) return from left subtree. We will search for node(1) and node(9) on right subtree. We go all the way to node(6), which is leaf node. At node(8), the left subtree returns nothing as none of the nodes in the left subtree of node(8). However, the right subtree returns node(9). As per our algorithm, if either of the subtrees returns a non-empty node, we return the node return from the subtree. At node(5), we get a non-empty node from the right subtree and we already know, from the left subtree, we got node(1). At this point at node(5), we have both left and right subtree returning non-empty node, hence return the node(5). Two nodes will be searched on the right subtree of node(10), which will return nothing, hence, final lowest common ancestor will be node(5).

### Implementation

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

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

typedef struct node Node;

Node * findLCA(Node *root, int val1, int val2)
{
// Base case
if (root == NULL) return NULL;

/* If either val1 or val2 matches with root's key,
report the presence by returning the root
(Note that if a key is the ancestor of other,
then the ancestor key becomes LCA
*/
if (root->key == val1 || root->key == val2)
return root;

// Look for keys in left and right subtrees
Node *left  = findLCA(root->left, val1, val2);
Node *right = findLCA(root->right, val1, val2);

/* If both of the above calls return Non-NULL,
then one key is present in once subtree
and other is present in other,
So this node is the LCA */
if (left && right)  return root;

// Otherwise check if left subtree or right subtree is LCA
return (left != NULL)? left : 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){
}
else{
}
}
return node;
}

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

printf("\n least common ancestor: %d ",
leastCommonAncestor(root, 15, 25));

return 0;
}
```

Below implementation only works for binary search tree and not for the binary tree as above method works.

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

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

typedef struct node Node;

int leastCommonAncestor(Node *root, int val1, int val2){

if(!root)
return -1;

if(root->value == val1 || root->value == val2)
return root->value;

/* Case 3: If one value is less and other greater
than the current node
Found the LCS return */
if((root->value > val1 && root->value <= val2) ||
(root->value <= val1 && root->value >val2)){
return root->value;
}
/*Case 2 : If Both values are greater than current node,
look in right subtree */
else if(root->value < val1 && root->value <val2){
return leastCommonAncestor(root->right, val1, val2);
}
/*Case 1 : If Both values are less than current node,
look in left subtree */
else if(root->value > val1 && root->value > val2){
return leastCommonAncestor(root->left, val1, val2);
}
}

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;
//Creating a binary tree

printf("\n least common ancestor: %d ",
leastCommonAncestor(root, 15, 25));

return 0;
}

```

The worst complexity of the algorithm to find the lowest common ancestor in a binary tree is O(n). Also, keep in mind that recursion is involved. More skewed the tree, more stack frames on the stack and more the chances that stack will overflow.

This problem is solved using on traversal of tree and managing states when returning from recursive calls.

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 1 Comment on Lowest common ancestor in binary tree

## Kth smallest element in a binary a search tree

Given a binary search tree, find kth smallest element in the binary search tree. For example, 5th smallest element in below binary search tree would be 14, if store the tree in sorted order 5,7,9,10,14,15,19; 14 is the fifth smallest element in that order.

### Kth smallest element in binary search tree: thoughts

As mentioned earlier in a lot of posts like delete a binary tree or mirror a binary tree, first try to find the traversal order required to solve this problem. One hint we already got is that we want all the nodes on BST traversed in sorted order. What kind of traversal gives us a sorted order of nodes? Of course, it is inorder traversal.

So idea is to do an inorder traversal of the binary search tree and store all the nodes in an array. Once traversal is finished, find the kth smallest element in the sorted array.

This approach, however, scans the entire tree and also has space complexity of O(n) because we store all the nodes of tree in an array. Can we avoid scanning the whole tree and storing nodes?

If we keep count of how many nodes are traversed during inorder traversal, we can actually stop traversal as soon as we see k nodes are visited. In this case, we do not store nodes, just a counter.

#### Kth smallest element in binary tree: implementation

```package com.company.BST;

import java.util.Stack;

/**
* Created by sangar on 9.11.18.
*/
public class FindKthSmallestInBST {
private int counter;

public FindKthSmallestInBST(){
counter = 0;
}
public TreeNode findKthSmallest(TreeNode root, int k){
if(root == null) return root;

//Traverse left subtree first
TreeNode left = findKthSmallest(root.getLeft(),k);
//If we found kth node on left subtree
if(left != null) return left;
//If k becomes zero, that means we have traversed k nodes.
if(++counter == k) return root;

return findKthSmallest(root.getRight(),k);
}
}
```

Test cases

```package test;

import com.company.BST.BinarySearchTree;
import com.company.BST.FindKthSmallestInBST;
import com.company.BST.TreeNode;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 23.9.18.
*/
public class KthSmallestElementTest {

FindKthSmallestInBST tester = new FindKthSmallestInBST();

@Test
public void kthSmallestElementTest() {

BinarySearchTree&lt;Integer&gt; binarySearchTree =
new BinarySearchTree&lt;&gt;();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

TreeNode kthNode =
tester.findKthSmallest(binarySearchTree.getRoot(),1);
assertEquals(6, kthNode.getValue());
}

@Test
public void kthSmallestElementOnRightSubtreeTest() {

BinarySearchTree&lt;Integer&gt; binarySearchTree =
new BinarySearchTree&lt;&gt;();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

TreeNode kthNode =
tester.findKthSmallest(binarySearchTree.getRoot(),5);
assertEquals(12, kthNode.getValue());
}

@Test
public void kthSmallestElementAbsentSubtreeTest() {

BinarySearchTree&lt;Integer&gt; binarySearchTree =
new BinarySearchTree&lt;&gt;();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

TreeNode kthNode =
tester.findKthSmallest(binarySearchTree.getRoot(),10);
assertEquals(null, kthNode);
}

@Test
public void kthSmallestElementNulltreeTest() {

BinarySearchTree&lt;Integer&gt; binarySearchTree =
new BinarySearchTree&lt;&gt;();
binarySearchTree.insert(10);
binarySearchTree.insert(8);
binarySearchTree.insert(15);
binarySearchTree.insert(12);
binarySearchTree.insert(6);
binarySearchTree.insert(9);

TreeNode kthNode = tester.findKthSmallest(null,10);
assertEquals(null, kthNode);
}
}
```

The complexity of this algorithm to find kth smallest element is `O(k)` as we traverse only k nodes on binary search tree.

There is hidden space complexity here. Recursive function requires call stack memory, which is limited to Operation System default. More deep you go in recursion, more space we use on stack. If tree is completely skewed, there are more chances of stack overflow. Also recursive function is very difficult to debug in production environments. Below is the non-recursive solution for the same problem.

#### Non-recursive way to find kth smallest element in BST

```public int kthSmallest(TreeNode root, int k) {
Stack&lt;TreeNode&gt; s = new Stack&lt;TreeNode&gt;();

TreeNode current = root;
int result = 0;

while(!s.isEmpty() || current!=null){
if(current!=null){
s.push(current);
current = current.getLeft();
}else{
TreeNode  temp = s.pop();
k--;
if(k==0)
result = (int)temp.getValue();
current = temp.getRight();
}
}

return result;
}
```

Please share if there is something wrong or missing. If you are preparing for an interview and need help, please reach out to us at [email protected]

Posted on Categories Binary Search Tree, Data Structures3 Comments on Find Kth smallest element in binary search tree