1
class Solution {
2
 public:
3
  int countNodes(TreeNode *root) {
4
    if (root == NULL) {
5
      return 0;
6
    }
7
    return countNodes(root->left) + countNodes(root->right) + 1;
8
  }
9

10
  bool findTarget(TreeNode *root, int k) {
11
    int totalCount = countNodes(root);
12
    int count = 0;
13
    stack<TreeNode *> inorder;
14
    stack<TreeNode *> revInorder;
15

16
    TreeNode *currNode = root;
17
    while (currNode != NULL) {
18
      inorder.push(currNode); // Store all elements in left of tree
19
      currNode = currNode->left;
20
    }
21

22
    currNode = root;
23
    while (currNode != NULL) {
24
      revInorder.push(currNode); // Store all elements in right of tree
25
      currNode = currNode->right;
26
    }
27

28
    while (count < totalCount - 1) {
29
      TreeNode *inordertop = inorder.top();
30
      TreeNode *revinordertop = revInorder.top();
31
      if (inordertop->val + revinordertop->val == k) { // If inordertop + revinordertop is equal to
32
                                                       // k, we have found a pair, so return true
33
        return true;
34
      } else if (inordertop->val + revinordertop->val >
35
                 k) { // If they are greater than k, we have to found a value
36
        // which is just smaller than revinordertop, which means we have to find
37
        // predecessor of revinordertop, as we have to reduce the sum to make it
38
        // equal to k
39
        TreeNode *currtop = revinordertop;
40
        count++;
41
        revInorder.pop();
42
        if (currtop->left) {
43
          currtop = currtop->left;
44
          while (currtop) {
45
            revInorder.push(currtop);
46
            currtop = currtop->right;
47
          }
48
        }
49
      } else {
50
        // If they are smaller than k, we have to found a value which is just
51
        // larger than inordertop, which means we have to find successor of
52
        // revinordertop, as we have to increase the sum to make it equal to k
53
        TreeNode *currtop = inordertop;
54
        count++;
55
        inorder.pop();
56
        if (currtop->right) {
57
          currtop = currtop->right;
58
          while (currtop) {
59
            inorder.push(currtop);
60
            currtop = currtop->left;
61
          }
62
        }
63
      }
64
    }
65
    return false;
66
  }
67
};