AlgoDaily - Binary Tree Inorder Traversal

Binary Tree Inorder Traversal (Easy)

Good afternoon! Here's our prompt for today.

You may see this problem at Flipkart, Slack, Netflix, Snap, Checkout Com, Digitate, Pagerduty, Seagate, Elastic, Anaplan, and Dell.

Can you write a function to traverse a binary tree in-order, and print out the value of each node as it passes?

SNIPPET

The example would output [4, 6, 5] since there is no left child for 4, and 6 is visited in-order before 5.

The definition of a tree node is as follows:

1struct Node {
2  int val;
3  Node* left = nullptr;
4  Node* right = nullptr;
5
6  Node(int val) : val(val) {}
7};

Follow up: you'll likely get the recursive solution first, could you do it iteratively?

Constraints

Number of vertices in the tree <= 100000
The values of the vertices in the tree will be between -1000000000 and 1000000000
Expected time complexity : O(n)
Expected space complexity : O(1)

xxxxxxxxxx
​
 
#include "gtest/gtest.h";
​
// available data structures
​
class Node {
public:
    int val;
    std::shared_ptr<Node> left;
    std::shared_ptr<Node> right;
​
    Node(int _val) : val(_val), left(nullptr), right(nullptr) { }
};
​
class BinaryTreeTest : public ::testing::Test {
protected:
    std::shared_ptr<Node> tree1;
    std::shared_ptr<Node> tree2;
    std::shared_ptr<Node> tree3;
    std::shared_ptr<Node> tree4;
    std::shared_ptr<Node> tree5;
​
    virtual void SetUp() {
        // Regular binary trees
        tree1.reset(new Node(4));
        tree1->left.reset(new Node(1));
        tree1->right.reset(new Node(3));
​

OUTPUT

Results will appear here.