data structure: Binary tree

Binary tree: at least two children of each node in the tree
binary search tree: for each node in the tree, the value of that node is smaller than all nodes in its right subtree and the value of that node is larger than all nodes in its left subtree.
complete binary tree: in every level of the tree, except possibly the last level, all nodes are completely filled, and the nodes are as far left as possible.
balanced binary tree: for each node in the tree, the height of its left subtree and the height of its right subtree differ by 1 or less.
Tree Tranversal:
pre-order, in-order, post-order.
These three traversal method both can be implemented by recursion. In some problems, we need to traverse the whole binary tree to get the result.

Q1 -> Q5 are basic recursion method used in the binary tree problems.
The basic idea is kind of like the pre-order traversal, check if the root node satisfy the requirement then check recursively check the left subtree and right subtree.
The rest questions of binary tree problem is the extension of the basic recursion method.
Q1: insert into binary search tree
Insert a key in a binary search tree if the binary search tree does not already contain the key. Return the root of the binary search tree.
analysis:
For most tree related problems, recursion is the simplest way to solve. Since each node in a tree has the same property, we can recursively search the root->left and root->right to get the answer. The problem apply to the whole tree can be apply to the left subtree and right subtree.
To insert a value into binary search tree, if the root is NULL, return the new node, else find the right position to insert the value, the right position to insert the value is left or right child of a leaf node. If the value of the root is < value, insert the value into the right subtree, if the value of the root is > value, insert the value into the left subtree, if the two value equals, no need to insert, return.
class Solution {
 private:
  void helper(TreeNode* &root, int value) {
//base case
    TreeNode* nnode = new TreeNode(value);
    if (root == NULL) {
      root = nnode;
    }
    //if value is larger than the value of root, insert the value into right subtree
    if (root->value < value)  helper(root->right, value);
    if (root->value > value)  helper(root->left, value);
    if (root->value == value) return;
    return;
  }
 public:
  TreeNode* insert(TreeNode* root, int value) {
    // Write your solution here.
    //step1: find the position first
    //step2: insert
    helper(root, value);
    return root;
  }
};
time complexity: O(logn)
space complexity: O(1)
Q2: search in binary search tree
find the target value in binary search tree, if the value is not in the tree, return NULL, else return the root.
class Solution {
 public:
  TreeNode* solve(TreeNode* root, int value) {
    //base case
    if (root == NULL) return NULL;
    if (root->value == value) return root;
    //recusive rule->subproblem
    if (root->value < value) return solve(root->right, value);
    if (root->value > value) return solve(root->left, value);
    return root;
  }
};
Time complexity: O(n) n is the total number of nodes in the binary tree
The recursion code is a pre-order traversal, the time complexity is equal to the time-complexity of pre-order traversal.
Space complexity: O(1)

Q3: Tweaked Identical Binary Trees
Determine whether two given binary trees are identical assuming any number of ‘tweak’s are allowed. A tweak is defined as a swap of the children of one node in the tree.

class Solution {
 public:
  bool isTweakedIdentical(TreeNode* r1, TreeNode* r2) {
    //base case
    if (r1 == NULL && r2 == NULL) return true;
    else if (r1 != NULL && r2 != NULL) {
      if (r1->value == r2->value) return (isTweakedIdentical(r1->left, r2-> right) && isTweakedIdentical(r1->right, r2->left)) || (isTweakedIdentical(r1->left, r2-> left) && isTweakedIdentical(r1->right, r2->right));
      else return false;
    }
    else return false;
    return 0;
  }
};
time complexity: O(n^2)
space complecity: O(1)

Q4: Is Binary Search Tree Or Not
Determine if a given binary tree is binary search tree.

analysis: the property of binary search tree is that each node in the tree, the value of that node is < value of all nodes in the right subtree and > value of all nodes in the left subtree. For each root node, maintain a lower bound and a upper bound. For nodes in left subtree, the upper bound is root value, the lower bound is the lower bound of root node; For nodes in right subtree, the lower bound is root value, the upper bound is the upper bound of root node.
class Solution {
 private:
  bool helper(TreeNode* root, int lower, int upper) {
    //base case
    if (root == NULL) return true;
    if (root->value < upper && root->value > lower) {
      return helper(root->left, lower, root->value) && helper(root->right, root->value, upper);
    }else return false;
  }
 public:
  bool isBST(TreeNode* root) {
    bool rst;
    return helper(root, INT_MIN, INT_MAX);
  }
};
TIME COMPLEXITY: O(n)
SPACE COMPLEXITY: O(1)
Q5: Get Keys In Binary Search Tree In Given Range
Get the list of keys in a given binary search tree in a given range[min, max] in ascending order, both min and max are inclusive.
analysis:
search all nodes with value < max and search all nodes with value > min, if the value of the node is >=min and <= max, push back into result. One thing to notice is that the result should be in ascending order, for binary search tree, the only traversal method to make the result in ascending order is in-order traversal. Therefore, the recursion should follow in-order traversal recursion method.
class Solution {
 private:
  void helper(vector<int> &rst, TreeNode* root, int min, int max) {
    //base case
    if (root == NULL) return;
    if (root->value > min) {
      helper(rst, root->left, min, max);
    }
    //in order to keep the result in ascending order, for binary search tree, we have to use inorder traversal
    if (root->value <= max && root->value >= min) rst.push_back(root->value);
    if (root->value < max) {
      helper(rst, root->right, min, max);
    }
   
  }
 public:
  vector<int> getRange(TreeNode* root, int min, int max) {
    //sanity check
    vector<int> rst;
    if (root == NULL) return rst;
    helper(rst, root, min, max);
    return rst;
  }
};
time complexity: O(n)
space complexity: O(1)