JavaScript Program to Transform a BST to Greater Sum Tree - Coding

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.

JavaScript

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.

JavaScript

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

Reffered: https://www.geeksforgeeks.org

JavaScript

Related
JavaScript Program to Count Distinct Elements in Every Window
JavaScript Program to Find Circular Rotation of an Array by K Positions
Reverse all the Words of Sentence JavaScript
JavaScript Program to Find the Next Power of Two
Maximum of all Subarrays of Size k using JavaScript

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	16