Maximum Binary Tree II LeetCode solution in C++

1
/**
2
 * Definition for a binary tree node.
3
 * struct TreeNode {
4
 * int val;
5
 * TreeNode *left;
6
 * TreeNode *right;
7
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
10
 * right(right) {}
11
 * };
12
 */
13
class Solution {
14
 public:
15
  void insertIntoMaxTreeRec(TreeNode *root, TreeNode *newNode) // o(logn)
16
  {
17
    if (!root) return;
18
    if (root->right && root->right->val < newNode->val) {
19
      newNode->left = root->right;
20
      root->right = newNode;
21

22
      return;
23
    }
24
    if (!root->right) {
25
      root->right = newNode;
26

27
      return;
28
    }
29

30
    insertIntoMaxTreeRec(root->right, newNode);
31
  }
32
  TreeNode *insertIntoMaxTree(TreeNode *root, int val) {
33
    TreeNode *curr = new TreeNode(val);
34

35
    if (root->val < val) {
36
      curr->left = root;
37
      root = curr;
38
    } else {
39
      insertIntoMaxTreeRec(root, curr);
40
    }
41
    return root;
42
  }
43
};