Coding Exercise - Search in a Binary Search Tree 编程练习题：二叉查找树BST

justyy (82)in #programming • 6 years ago (edited)

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:

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

C/C++ Definition of a Binary Tree Node

A Binary tree can be recursively defined using struct.

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

Recursion

The Binary Search Tree (BST) 's one important characteristics: the left node is smaller than the parent and the right node is larger than the parent. So, instead of searching the entire tree, we can cut one branch at each iteration, to reduce to complexity from O(n) to O(logn).

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

Iterative

You can convert above recursion to iterative implementation using Stack - pushing one subtree to the stack.

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        stack<TreeNode*> st;
        st.push(root);
        while (st.size() > 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;
    }
};

As the task is to find the element in the tree, and each iteration, you only search one branch (and cut another branch), you can use Queue as well.

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

Support me and my work as a witness - witness thread by

voting me here, or
voting me as a witness proxy - let @justyy represent you.

Thank you! Some of My Contributions: SteemIt Tutorials, Robots, Tools and APIs

// Reposted to https://helloacm.com/c-c-coding-exercise-search-in-a-binary-search-tree/ for better indexing.

题意：给定一个二分查找树 BST, Binary Search Tree, 查找指定的元素，返回该节点开始的子树。如果没找到就返回NULL。

二叉树在C/C++中的定义

二叉树可以用结构体来定义，其中左右子树都是递归的定义。

 struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

递归

二叉查找树BST的最重要的特性就是左节点比根节点小，而右节点比根子树大。这样我们就可以每次根据根节点的大小，相应的在左子树或者右子树中递归查找。每次都摒弃一棵子树，这样时间复杂度大约是 O(logn) ，如果遍历所有的节点则时间复杂度 O(n).

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

迭代

递归实现可以用迭代来实现，自己操作堆栈，每子把左子树或者右子树添加到堆栈中。

class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == nullptr) return NULL;
        stack<TreeNode*> st;
        st.push(root);
        while (st.size() > 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;
    }
};

由于这题和搜索的顺序关系不太大，我们还可以用队列来实现，按层来查找。

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

// Reposted to: https://justyy.com/archives/6465