This content originally appeared on DEV Community and was authored by Mehran Ghamaty
Learning how to traverse a tree can answer a huge number of interview questions; At the high level there are two main ways of traversing a Tree depth first search and breadth first search.
To give some meat to our article let's give our Nodes a definition;
template<typename T>
struct MyTreeNode {
unique_ptr<T> value;
shared_ptr<MyTreeNode> left;
shared_ptr<MyTreeNode> right;
MyTreeNode(): val(make_ptr(nullptr)), left(make_ptr(nullptr)), right(make_ptr(nullptr)) {}
MyTreeNode(T val): val(make_ptr(pulltr), left(make_ptr(nullptr)), right(make_ptr(nullptr)) {}
MyTreeNode(T val, MyTreeNode left, MyTreeNode right): val(make_ptr(pulltr), left(make_ptr(left)), right(make_ptr(right)) {}
}
Lets start with breadth-first search since this non-recursive solution is sometimes easier to debug during a stressful interview, even if it's slightly more difficult to remember.
template<typename T>
void breadth_first_search(shared_ptr<MyTreeNode> root,
const std::function<void(T)>& predicate) {
if(root.get() == nullptr()) {
return;
}
vector<shared_ptr<MyTreeNode>> queue;
queue.push(root);
while(!queue.empty()) {
#ifdef pre-order
predicate(queue.front().value.get());
queue.pop();
#endif
if(root.left.get() != nullptr) {
queue.push(root.left);
}
#ifdef in-order
predicate(queue.front().value.get());
queue.pop();
#endif
if(root.right.get() != nullptr) {
queue.push(root.right);
}
#ifdef post-order
predicate(queue.front().value.get());
queue.pop()
#endif
}
}
Next example would be depth-first search;
template<typename T>
void depth_first_search(shared_ptr<MyTreeNode> root,
const std::function<void(T)>& predicate) {'
if(root.get() != nullptr) {
return;
}
// if pre-order
#ifdef pre-order
predicate(root.value.get());
#endif
if(root.left.get() != nullptr) {
depth_first_search(root.left);
}
#ifdef in-order
predicate(root.value.get());
#endif
if(root.right.get() != nullptr) {
depth_first_search(root.right);
}
#ifdef post-order
predicate(root.value.get());
#endif
}
Now these two algorithm serve as the basis for many problems.
This content originally appeared on DEV Community and was authored by Mehran Ghamaty
Mehran Ghamaty | Sciencx (2025-02-26T22:14:36+00:00) Trees: Interview Problem Survey. Retrieved from https://www.scien.cx/2025/02/26/trees-interview-problem-survey/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.