sharp/bstToLL.cpp at master · manudhundi/sharp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 /******************************************************************
 * Binary Tree into LL (done IN PLACE)
 *
 *
 *         1
 *        / \
 *       2   5
 *      / \   \
 *     3   4   6
 *
 *       to
 *   1
 *    \
 *     2
 *      \
 *       3
 *        \
 *         4
 *          \
 *           5
 *            \
 *             6
 ******************************************************************/


/**
 * Definition for binary tree
 * /
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

void flatten(TreeNode *root) {
  TreeNode *curNode = root;
  TreeNode *leftNode = NULL;
  TreeNode *rightNode = NULL;
  while (curNode) {
    leftNode = curNode->left;
    /* If there is no left node then we just continue to right sub tree */
    if (leftNode) {
      if (curNode->right) {
        /* Make the rightmost node in the left subtree point to right node
        Because as per our need we go the right child only after we are done
        with all elements in the left subtree */
        rightNode = leftNode;
        while (rightNode->right) {
          rightNode = rightNode->right;
        }
        rightNode->right = curNode->right;
      }
      /* Make the left child the right child */
      curNode->right = leftNode;
      curNode->left = NULL;
    }
    /* We no longer have left subtree */
    curNode = curNode->right;
  }
}