aboutsummaryrefslogtreecommitdiff
path: root/bst_greater_sum_tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'bst_greater_sum_tree.c')
-rw-r--r--bst_greater_sum_tree.c33
1 files changed, 33 insertions, 0 deletions
diff --git a/bst_greater_sum_tree.c b/bst_greater_sum_tree.c
new file mode 100644
index 0000000..713c582
--- /dev/null
+++ b/bst_greater_sum_tree.c
@@ -0,0 +1,33 @@
+// 1038. Binary Search Tree to Greater Sum Tree
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary search tree, convert it to a greater tree such
+ * that every key o the original bst is changed to the original key plus the sum
+ * of all keys greater than the original key in bst. as a reminder, a binary
+ * search tree is a tree that satisfies the following constraints. the left
+ * subtree of a node contains only nodes with keys less than the node's key. the
+ * right subtree of a node contains only nodes with keys greater than the node's
+ * key. both the left and right subtrees also be binary search trees.
+ */
+
+struct TreeNode {
+ int val;
+ struct TreeNode *left;
+ struct TreeNode *right;
+};
+
+struct TreeNode *dfs(struct TreeNode *root) {
+ int accum = 0;
+ if (!root)
+ return NULL;
+ else {
+ dfs(root->right);
+ accum += root->val;
+ root->val = accum;
+ dfs(root->left);
+ return root;
+ }
+}
+
+struct TreeNode *bstToGst(struct TreeNode *root) { return dfs(root); }