binary tree & binary search tree

[nnop]

Node

struct Node {
    int data;
    shared_ptr<Node> left;
    shared_ptr<Node> right;
    Node(int val) : data(val) {}
};

[nnop]

compare two trees

bool comp_node(const shared_ptr<Node>& root1, const shared_ptr<Node>& root2) {
    if (root1 == root2)
        return true;

    if (root1 == nullptr || root2 == nullptr)
        return false;

    return root1->data == root2->data &&
           comp_node(root1->left, root2->left) && 
           comp_node(root1->right, root2->right);
}

[nnop]

insert to a BST

void insert(shared_ptr<Node>& node, int value) {
    if (node == nullptr) {
        node = make_shared<Node>(value);
        return;
    }

    if (value < node->data) {
        insert(node->left, value);
    } else {
        insert(node->right, value);
    }
}

search in a BST

shared_ptr<Node> search(const shared_ptr<Node>& node, int value) {
    if (node == nullptr || node->data == value)
        return node;

    if (value < node->data)
        return search(node->left, value);
    else 
        return search(node->right, value);
}

[nnop]

in-order DFS

void dfs(const shared_ptr<Node>& node) {
    if (node == nullptr) return;

    if (node->left)
        dfs(node->left);
    cout << node->data << endl;
    if (node->right)
        dfs(node->right);
}