JavaScript Program to Transform a BST to Greater Sum Tree
Given a BST, transform it into a greater sum tree where each node contains the sum of all nodes greater than that node.
Table of Content
- Using iterative approach
- Using recursion
Using iterative approach
In this approach we start with the rightmost node of the BST and initialize the sum to 0. We use a stack to perform iterative reverse inorder traversal. At each node, we update its value with the sum of all greater values and then update the sum with the current node’s value. We continue moving to the left child if it exists.
Example: Implementation of program to Transform a BST to greater sum tree using Iterative approach.
class Node {
constructor(item) {
this.data = item;
this.left = null;
this.right = null;
}
}
function transform(root) {
let sum = 0;
const stack = [];
let current = root;
while (current || stack.length > 0) {
while (current) {
stack.push(current);
current = current.right;
}
current = stack.pop();
sum += current.data;
current.data = sum - current.data;
current = current.left;
}
}
function inorder(root) {
if (root == null)
return;
inorder(root.left);
console.log(root.data + " ");
inorder(root.right);
}
let Root = new Node(11);
Root.left = new Node(2);
Root.right = new Node(29);
Root.left.left = new Node(1);
Root.left.right = new Node(7);
Root.right.left = new Node(15);
Root.right.right = new Node(40);
Root.right.right.left = new Node(35);
console.log("Inorder Traversal of given tree:");
inorder(Root);
transform(Root);
console.log("\nInorder Traversal of transformed tree:");
inorder(Root);
Output
Inorder Traversal of given tree: 1 2 7 11 15 29 35 40 Inorder Traversal of transformed tree: 139 137 130 119 104 75 40 0
Time Complexity: O(N), where N is the number of nodes in the BST.
Auxiliary Space: O(H), where H is the height of the BST.
Using recursion
In this approach we traverse BST in reverse inorder recursively. At each node, we update its value with the sum of all greater values and store the old sum in the current node. We then recur for the left subtree.
Example: Implementation of program to Transform a BST to greater sum tree using recursion.
class Node {
constructor(item) {
this.data = item;
this.left = null;
this.right = null;
}
}
let sum = 0;
let Root;
function transformUtil(root) {
if (root == null)
return;
transformUtil(root.right);
sum = sum + root.data;
root.data = sum - root.data;
transformUtil(root.left);
}
function transform(root) {
transformUtil(root);
}
function inorder(root) {
if (root == null)
return;
inorder(root.left);
console.log(root.data + " ");
inorder(root.right);
}
Root = new Node(11);
Root.left = new Node(2);
Root.right = new Node(29);
Root.left.left = new Node(1);
Root.left.right = new Node(7);
Root.right.left = new Node(15);
Root.right.right = new Node(40);
Root.right.right.left = new Node(35);
console.log("Inorder Traversal of given tree:");
inorder(Root);
transform(Root);
console.log("\nInorder Traversal of transformed tree:");
inorder(Root);
Output
Inorder Traversal of given tree: 1 2 7 11 15 29 35 40 Inorder Traversal of transformed tree: 139 137 130 119 104 75 40 0
Time Complexity: O(n) where n is the number of nodes in given Binary Tree, as it does a simple traversal of the tree.
Auxiliary Space: O(h) where h is the height of given Binary Tree due to Recursion
Contact Us