# Find the closest element in Binary Search Tree | Space Efficient Method

Given a binary search tree and a target node K. The task is to find the node with the minimum absolute difference with given target value K.**NOTE: **The approach used should have constant extra space consumed O(1). No recursion or stack/queue like containers should be used.

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

**Examples:**

Input: k = 4 Output: 4 Input: k = 18 Output: 17

A simple solution mentioned in this post uses recursion to get the closest element to a key in Binary search tree. The method used in the above mentioned post consumes O(n) extra space due to recursion.

Now we can easily modify the above mentioned approach using Morris traversal which is a space efficient approach to do inorder tree traversal without using recursion or stack/queue in constant space O(1).

Morris traversal is based on Threaded Binary trees which makes use of NULL pointers in a tree to make them point to some successor or predecessor nodes. As in a binary tree with n nodes, n+1 NULL pointers waste memory.

In the algorithm mentioned below we simply do inorder tree traversal and while doing inorder tree traversal using Morris Traversal we check for differences between the node’s data and the key and maintain two variables ‘diff’ and ‘closest’ which are updated when we find a closer node to the key. When we are done with the complete inorder tree traversal we have the closest node.**Algorithm** :

1) Initialize Current as root. 2) Initialize a variable diff as INT_MAX. 3)initialize a variable closest(pointer to node) which will be returned. 4) While current is not NULL: 4.1) If the current has no left child: a) If the absolute difference between current's data and the key is smaller than diff: 1) Set diff as the absolute difference between the current node and the key. 2) Set closest as the current node. b)Otherwise, Move to the right child of current. 4.2) Else, here we have 2 cases: a) Find the inorder predecessor of the current node. Inorder predecessor is the rightmost node in the left subtree or left child itself. b) If the right child of the inorder predecessor is NULL: 1) Set current as the right child of its inorder predecessor(Making threads between nodes). 2) Move current node to its left child. c) Else, if the threaded link between the current node and it's inorder predecessor already exists : 1) Set right pointer of the inorder predecessor node as NULL. 2) If the absolute difference between current's data and the key is smaller than diff: a) Set diff variable as the absolute difference between the current node and the key. b) Set closest as the current node. 3) Move current to its right child. 5)By the time we have traversed the whole tree, we have the closest node, so we simply return closest.

Below is the implementation of above approach:

## C++

`// CPP program to find closest value in` `// a Binary Search Tree.` `#include <iostream>` `#include <limits.h>` `using` `namespace` `std;` `// Tree Node` `struct` `Node {` ` ` `int` `data;` ` ` `Node *left, *right;` `};` `// Utility function to create a new Node` `Node* newNode(` `int` `data)` `{` ` ` `Node* temp = ` `new` `Node();` ` ` `temp->data = data;` ` ` `temp->left = temp->right = NULL;` ` ` `return` `temp;` `}` `// Function to find the Node closest to the` `// given key in BST using Morris Traversal` `Node* closestNodeUsingMorrisTraversal(Node* root,` ` ` `int` `key)` `{` ` ` `int` `diff = INT_MAX;` ` ` `Node* curr = root;` ` ` `Node* closest;` ` ` `while` `(curr) {` ` ` `if` `(curr->left == NULL) {` ` ` `// updating diff if the current diff is` ` ` `// smaller than prev difference` ` ` `if` `(diff > ` `abs` `(curr->data - key)) {` ` ` `diff = ` `abs` `(curr->data - key);` ` ` `closest = curr;` ` ` `}` ` ` `curr = curr->right;` ` ` `}` ` ` `else` `{` ` ` `// finding the inorder predecessor` ` ` `Node* pre = curr->left;` ` ` `while` `(pre->right != NULL &&` ` ` `pre->right != curr)` ` ` `pre = pre->right;` ` ` `if` `(pre->right == NULL) {` ` ` `pre->right = curr;` ` ` `curr = curr->left;` ` ` `}` ` ` `// threaded link between curr and` ` ` `// its predecessor already exists` ` ` `else` `{` ` ` `pre->right = NULL;` ` ` `// if a closer Node found, then update` ` ` `// the diff and set closest to current` ` ` `if` `(diff > ` `abs` `(curr->data - key)) {` ` ` `diff = ` `abs` `(curr->data - key);` ` ` `closest = curr;` ` ` `}` ` ` `// moving to the right child` ` ` `curr = curr->right;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `closest;` `}` `// Driver Code` `int` `main()` `{` ` ` `/* Constructed binary tree is` ` ` `5` ` ` `/ \` ` ` `3 9` ` ` `/ \ / \` ` ` `1 2 8 12 */` ` ` `Node* root = newNode(5);` ` ` `root->left = newNode(3);` ` ` `root->right = newNode(9);` ` ` `root->left->left = newNode(1);` ` ` `root->left->right = newNode(2);` ` ` `root->right->left = newNode(8);` ` ` `root->right->right = newNode(12);` ` ` `cout << closestNodeUsingMorrisTraversal(root, 10)->data;` ` ` `return` `0;` `}` |

## Java

`// Java program to find closest value in` `// a Binary Search Tree.` `class` `GFG` `{` `// Tree Node` `static` `class` `Node` `{` ` ` `int` `data;` ` ` `Node left, right;` `};` `// Utility function to create a new Node` `static` `Node newNode(` `int` `data)` `{` ` ` `Node temp = ` `new` `Node();` ` ` `temp.data = data;` ` ` `temp.left = temp.right = ` `null` `;` ` ` `return` `temp;` `}` `// Function to find the Node closest to the` `// given key in BST using Morris Traversal` `static` `Node closestNodeUsingMorrisTraversal(Node root,` ` ` `int` `key)` `{` ` ` `int` `diff = Integer.MAX_VALUE;` ` ` `Node curr = root;` ` ` `Node closest = ` `null` `;` ` ` `while` `(curr != ` `null` `)` ` ` `{` ` ` `if` `(curr.left == ` `null` `)` ` ` `{` ` ` `// updating diff if the current diff is` ` ` `// smaller than prev difference` ` ` `if` `(diff > Math.abs(curr.data - key))` ` ` `{` ` ` `diff = Math.abs(curr.data - key);` ` ` `closest = curr;` ` ` `}` ` ` `curr = curr.right;` ` ` `}` ` ` `else` ` ` `{` ` ` `// finding the inorder predecessor` ` ` `Node pre = curr.left;` ` ` `while` `(pre.right != ` `null` `&&` ` ` `pre.right != curr)` ` ` `pre = pre.right;` ` ` `if` `(pre.right == ` `null` `)` ` ` `{` ` ` `pre.right = curr;` ` ` `curr = curr.left;` ` ` `}` ` ` `// threaded link between curr and` ` ` `// its predecessor already exists` ` ` `else` ` ` `{` ` ` `pre.right = ` `null` `;` ` ` `// if a closer Node found, then update` ` ` `// the diff and set closest to current` ` ` `if` `(diff > Math.abs(curr.data - key))` ` ` `{` ` ` `diff = Math.abs(curr.data - key);` ` ` `closest = curr;` ` ` `}` ` ` `// moving to the right child` ` ` `curr = curr.right;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `closest;` `}` `// Driver Code` `public` `static` `void` `main(String[] args)` `{` ` ` `/* Constructed binary tree is` ` ` `5` ` ` `/ \` ` ` `3 9` ` ` `/ \ / \` ` ` `1 2 8 12 */` ` ` `Node root = newNode(` `5` `);` ` ` `root.left = newNode(` `3` `);` ` ` `root.right = newNode(` `9` `);` ` ` `root.left.left = newNode(` `1` `);` ` ` `root.left.right = newNode(` `2` `);` ` ` `root.right.left = newNode(` `8` `);` ` ` `root.right.right = newNode(` `12` `);` ` ` `System.out.println(closestNodeUsingMorrisTraversal(root, ` `10` `).data);` `}` `}` `// This code is contributed by Rajput-Ji` |

## Python3

`# Python program to find closest value in` `# Binary search Tree` `_MIN ` `=` `-` `2147483648` `_MAX ` `=` `2147483648` `# Helper function that allocates a new` `# node with the given data and None left` `# and right poers. ` `class` `newNode:` ` ` `# Constructor to create a new node` ` ` `def` `__init__(` `self` `, data):` ` ` `self` `.data ` `=` `data` ` ` `self` `.left ` `=` `None` ` ` `self` `.right ` `=` `None` `# Function to find the Node closest to the` `# given key in BST using Morris Traversal` `def` `closestNodeUsingMorrisTraversal(root,key):` ` ` `diff ` `=` `_MAX` ` ` `curr ` `=` `root` ` ` `closest` `=` `0` ` ` `while` `(curr) :` ` ` `if` `(curr.left ` `=` `=` `None` `) :` ` ` `# updating diff if the current diff is` ` ` `# smaller than prev difference` ` ` `if` `(diff > ` `abs` `(curr.data ` `-` `key)) :` ` ` `diff ` `=` `abs` `(curr.data ` `-` `key)` ` ` `closest ` `=` `curr` ` ` ` ` `curr ` `=` `curr.right` ` ` ` ` `else` `:` ` ` `# finding the inorder predecessor` ` ` `pre ` `=` `curr.left` ` ` `while` `(pre.right !` `=` `None` `and` ` ` `pre.right !` `=` `curr):` ` ` `pre ` `=` `pre.right` ` ` `if` `(pre.right ` `=` `=` `None` `):` ` ` `pre.right ` `=` `curr` ` ` `curr ` `=` `curr.left` ` ` ` ` `# threaded link between curr and` ` ` `# its predecessor already exists` ` ` `else` `:` ` ` `pre.right ` `=` `None` ` ` `# if a closer Node found, then update` ` ` `# the diff and set closest to current` ` ` `if` `(diff > ` `abs` `(curr.data ` `-` `key)) :` ` ` `diff ` `=` `abs` `(curr.data ` `-` `key)` ` ` `closest ` `=` `curr` ` ` ` ` `# moving to the right child` ` ` `curr ` `=` `curr.right` ` ` ` ` `return` `closest` ` ` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `""" /* Constructed binary tree is` ` ` `5` ` ` `/ \` ` ` `3 9` ` ` `/ \ / \` ` ` `1 2 8 12 */ """` ` ` ` ` `root ` `=` `newNode(` `5` `)` ` ` `root.left ` `=` `newNode(` `3` `)` ` ` `root.right ` `=` `newNode(` `9` `)` ` ` `root.left.right ` `=` `newNode(` `2` `)` ` ` `root.left.left ` `=` `newNode(` `1` `)` ` ` `root.right.right ` `=` `newNode(` `12` `)` ` ` `root.right.left ` `=` `newNode(` `8` `)` ` ` `print` `(closestNodeUsingMorrisTraversal(root, ` `10` `).data)` `# This code is contributed` `# Shubham Singh(SHUBHAMSINGH10)` |

## C#

`// C# program to find closest value in` `// a Binary Search Tree.` `using` `System;` ` ` `class` `GFG` `{` `// Tree Node` `public` `class` `Node` `{` ` ` `public` `int` `data;` ` ` `public` `Node left, right;` `};` `// Utility function to create a new Node` `static` `Node newNode(` `int` `data)` `{` ` ` `Node temp = ` `new` `Node();` ` ` `temp.data = data;` ` ` `temp.left = temp.right = ` `null` `;` ` ` `return` `temp;` `}` `// Function to find the Node closest to the` `// given key in BST using Morris Traversal` `static` `Node closestNodeUsingMorrisTraversal(Node root,` ` ` `int` `key)` `{` ` ` `int` `diff = ` `int` `.MaxValue;` ` ` `Node curr = root;` ` ` `Node closest = ` `null` `;` ` ` `while` `(curr != ` `null` `)` ` ` `{` ` ` `if` `(curr.left == ` `null` `)` ` ` `{` ` ` `// updating diff if the current diff is` ` ` `// smaller than prev difference` ` ` `if` `(diff > Math.Abs(curr.data - key))` ` ` `{` ` ` `diff = Math.Abs(curr.data - key);` ` ` `closest = curr;` ` ` `}` ` ` `curr = curr.right;` ` ` `}` ` ` `else` ` ` `{` ` ` `// finding the inorder predecessor` ` ` `Node pre = curr.left;` ` ` `while` `(pre.right != ` `null` `&&` ` ` `pre.right != curr)` ` ` `pre = pre.right;` ` ` `if` `(pre.right == ` `null` `)` ` ` `{` ` ` `pre.right = curr;` ` ` `curr = curr.left;` ` ` `}` ` ` `// threaded link between curr and` ` ` `// its predecessor already exists` ` ` `else` ` ` `{` ` ` `pre.right = ` `null` `;` ` ` `// if a closer Node found, then update` ` ` `// the diff and set closest to current` ` ` `if` `(diff > Math.Abs(curr.data - key))` ` ` `{` ` ` `diff = Math.Abs(curr.data - key);` ` ` `closest = curr;` ` ` `}` ` ` `// moving to the right child` ` ` `curr = curr.right;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `closest;` `}` `// Driver Code` `public` `static` `void` `Main(String[] args)` `{` ` ` `/* Constructed binary tree is` ` ` `5` ` ` `/ \` ` ` `3 9` ` ` `/ \ / \` ` ` `1 2 8 12 */` ` ` `Node root = newNode(5);` ` ` `root.left = newNode(3);` ` ` `root.right = newNode(9);` ` ` `root.left.left = newNode(1);` ` ` `root.left.right = newNode(2);` ` ` `root.right.left = newNode(8);` ` ` `root.right.right = newNode(12);` ` ` `Console.WriteLine(closestNodeUsingMorrisTraversal(root, 10).data);` `}` `}` `/* This code is contributed by PrinciRaj1992 */` |

## Javascript

`<script>` `// Javascript program to find closest value in` `// a Binary Search Tree.` `// Tree Node` `class Node` `{` ` ` `constructor()` ` ` `{` ` ` `this` `.data = 0;` ` ` `this` `.left = ` `null` `;` ` ` `this` `.right = ` `null` `;` ` ` `}` `};` `// Utility function to create a new Node` `function` `newNode(data)` `{` ` ` `var` `temp = ` `new` `Node();` ` ` `temp.data = data;` ` ` `temp.left = temp.right = ` `null` `;` ` ` `return` `temp;` `}` `// Function to find the Node closest to the` `// given key in BST using Morris Traversal` `function` `closestNodeUsingMorrisTraversal(root, key)` `{` ` ` `var` `diff = 1000000000;` ` ` `var` `curr = root;` ` ` `var` `closest = ` `null` `;` ` ` `while` `(curr != ` `null` `)` ` ` `{` ` ` `if` `(curr.left == ` `null` `)` ` ` `{` ` ` `// updating diff if the current diff is` ` ` `// smaller than prev difference` ` ` `if` `(diff > Math.abs(curr.data - key))` ` ` `{` ` ` `diff = Math.abs(curr.data - key);` ` ` `closest = curr;` ` ` `}` ` ` `curr = curr.right;` ` ` `}` ` ` `else` ` ` `{` ` ` `// finding the inorder predecessor` ` ` `var` `pre = curr.left;` ` ` `while` `(pre.right != ` `null` `&&` ` ` `pre.right != curr)` ` ` `pre = pre.right;` ` ` `if` `(pre.right == ` `null` `)` ` ` `{` ` ` `pre.right = curr;` ` ` `curr = curr.left;` ` ` `}` ` ` `// threaded link between curr and` ` ` `// its predecessor already exists` ` ` `else` ` ` `{` ` ` `pre.right = ` `null` `;` ` ` `// if a closer Node found, then update` ` ` `// the diff and set closest to current` ` ` `if` `(diff > Math.abs(curr.data - key))` ` ` `{` ` ` `diff = Math.abs(curr.data - key);` ` ` `closest = curr;` ` ` `}` ` ` `// moving to the right child` ` ` `curr = curr.right;` ` ` `}` ` ` `}` ` ` `}` ` ` `return` `closest;` `}` `// Driver Code` `/* Constructed binary tree is` ` ` `5` ` ` `/ \` `3 9` `/ \ / \` `1 2 8 12 */` `var` `root = newNode(5);` `root.left = newNode(3);` `root.right = newNode(9);` `root.left.left = newNode(1);` `root.left.right = newNode(2);` `root.right.left = newNode(8);` `root.right.right = newNode(12);` `document.write(closestNodeUsingMorrisTraversal(root, 10).data);` `// This code is contributed by itsok.` `</script>` |

**Output:**

9

**Time Complexity**: O(n) **Auxiliary Space** : O(1)