How to Search in a Binary Search Tree?

  • 时间：2020-10-05 13:15:44
  • 分类：网络文摘
  • 阅读：95 次

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

推荐阅读：
wordpress主题制作时调用分类链接的方法　 两种方法批量删除wordpress自定义栏目　 如何获取wordpress外循环的自定义栏目　 为wordpress媒体文件添加分类目录和标签的方法　 小技巧：在wordpress仪表盘中双击评论内容可编辑评论　 解决wordpress自动更新失败无法进入后台的方法及升级失败原因　 通过.htaccess限制访问IP 保护wordpress后台安全　 第一次坐公交车作文100字　 人生思考作文800字　 上海东方明珠塔作文400字　
评论列表
添加评论