learn-to-code
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 3And the value to search: 2
You should return this subtree:2 / \ 1 3In 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.
1 2 3 4 5 6 | struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; |
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).
1 2 3 4 5 6 7 8 | 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;
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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;
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | 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; } }; |
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;
}
};You may also like: C/C++ 编程练习题：二叉查找树BST
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: C++ Coding Exercise - How to Merge Two Binary Trees?
Next Post: What Personal Data Might be Revealed While Surfing The Net