Home
How to Search in a Binary Search Tree?
Tags:, , , ,

How to Search in a Binary Search Tree?

April 7, 2019 No Comments algorithms, javascript

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:

        4
       / \
      2   7
     / \
    1   3

And the value to search: 2
You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.

Search in Binary Search Tree using Recursion

The Binary Search Tree is recursion by itself. Given a value, we can walk through BST by comparing the value to the current node, if it is smaller, the value might be in the left tree, if it is bigger, it might be in the right tree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (root === null) return null;
    if (root.val === val) return root;
    if (val < root.val) return searchBST(root.left, val);
    return searchBST(root.right, val);
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    if (root === null) return null;
    if (root.val === val) return root;
    if (val < root.val) return searchBST(root.left, val);
    return searchBST(root.right, val);
};

If we have reached the leaf nodes, we don’t find the value, simply return NULL. Using the stacks yield O(N) space complexity where the BST may be a singly-direction linked-list.

Iterative Search in Binary Search Tree

The same idea can be implemented using the iterative approach, where the usage of stacks is eliminated. The space complexity is O(1) constant.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    while (root !== null) {
        if (root.val === val) return root;
        if (val < root.val) {
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return null;
};
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var searchBST = function(root, val) {
    while (root !== null) {
        if (root.val === val) return root;
        if (val < root.val) {
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return null;
};

Both implementations run at O(N) time complexity where in the worst cases, N nodes have to be traversed (the binary search tree is de-generated into a single direction link list).

Search in BST (Java Implementation – Recursion)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (val == root.val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }
}
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (val == root.val) {
            return root;
        }
        if (val < root.val) {
            return searchBST(root.left, val);
        }
        return searchBST(root.right, val);
    }
}

Search in BST (C++ Implementation – Recursion)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        if (root->val == val) return root;
        return val > root->val ? searchBST(root->right, val) : searchBST(root->left, val);
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        if (root->val == val) return root;
        return val > root->val ? searchBST(root->right, val) : searchBST(root->left, val);
    }
};

Search in BST (Iterative Using Stack)

The following C++ implementation uses a Stack to iteratively push the correct branch. O(N) space complexity and O(N) time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        stack<TreeNode*> st;
        st.push(root);
        while (st.size() *gt; 0) {
            auto cur = st.top();
            st.pop();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                st.push(cur->right);
            } else {
                st.push(cur->left);
            }
        }
        return NULL;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        stack<TreeNode*> st;
        st.push(root);
        while (st.size() *gt; 0) {
            auto cur = st.top();
            st.pop();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                st.push(cur->right);
            } else {
                st.push(cur->left);
            }
        }
        return NULL;
    }
};

Search in BST (Iterative Using Double-Ended Queue)

As long as we push the correct pointer when navigating through the tree, we can use any other containers such as Queue or Double-ended queues, for example, the following C++ implementation makes use of the double-ended queues e.g. deque, and the solution still is accepted to search the values in a Binary Search Tree. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        deque<TreeNode*> Q;
        Q.push_back(root);
        while (Q.size() > 0) {
            auto cur = Q.front();
            Q.pop_front();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                Q.push_back(cur->right);
            } else {
                Q.push_back(cur->left);
            }
        }
        return NULL;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        deque<TreeNode*> Q;
        Q.push_back(root);
        while (Q.size() > 0) {
            auto cur = Q.front();
            Q.pop_front();
            if (cur == nullptr) continue;
            if (val == cur->val) {
                return cur;
            }            
            if (val > cur->val) {
                Q.push_back(cur->right);
            } else {
                Q.push_back(cur->left);
            }
        }
        return NULL;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
870 words
Last Post: How to Determine Sum of Two Square Numbers?
Next Post: How to Be Unpopular in the Coding World?

The Permanent URL is: How to Search in a Binary Search Tree?

Related posts:

  1. Fixing Profile Query Command due to API Change in Steem Blockchain Due to an API change in SteemIt see this post, the following code to get...
  2. Teaching Kids Programming – Closest Binary Search Tree Value (Recursion + Inorder Traversal + Binary Search Algorithm) Teaching Kids Programming: Videos on Data Structures and Algorithms Given the root of a binary...
  3. Algorithms to Determine a Palindrome Number Determine whether an integer is a palindrome. An integer is a palindrome when it reads...
  4. The Secure Shell (SSH) Chrome Extension developed by Google Speaking about SSH tools, we often use the PuTTY or Termius, which are heavy weight...
  5. You need a Numeric Keypad to Start with Your HHKB! Getting a HHKB and being excited for a few days? Sooner or later, you ‘ll...
  6. The Young Prompt Engineers My sons were excited to show me the Text to Image feature using Microsoft Bing....
  7. The Review of cozmo robot from Anki The ANKI COZMO robot is fun – I got it from Amazon and it is...
  8. Teaching Kids Programming – Algorithms to Find the Lowest Common Ancestor of a Binary Search Tree Teaching Kids Programming: Videos on Data Structures and Algorithms Given a binary search tree (BST),...

Leave a Reply