Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/538.html

538. Convert BST to Greater Tree

Level

Easy

Description

Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Solution

Same but just left/right mirror of https://leetcode.ca/2016-03-03-94-Binary-Tree-Inorder-Traversal

Begin by obtaining the inorder traversal of the binary search tree. This traversal lists all the nodes of the tree in ascending order based on their values.

Next, iterate over the inorder traversal in reverse order, skipping the last node (which corresponds to the highest value node in the original tree). For each node, find its immediate successor in the inorder traversal (i.e., the next node in the forward direction) and add its value to the node’s own value. After this operation, the node’s value will be updated to its original value plus the sum of all values greater than its own value in the original tree.

Finally, return the modified root node of the binary search tree.

• Java
• C++
• Python
• Go
• Javascript

• public class Convert_BST_to_Greater_Tree {
      /**
       * Definition for a binary tree node.
       * public class TreeNode {
       *     int val;
       *     TreeNode left;
       *     TreeNode right;
       *     TreeNode(int x) { val = x; }
       * }
       */
      class Solution {
  
          int sum = 0;
  
          public TreeNode convertBST(TreeNode root) {
              if (root == null) {
                  return null;
              }
  
              convertBST(root.right);
              sum += root.val;
              root.val = sum;
              convertBST(root.left);
  
              return root;
          }
      }
  }
  
  ############
  
  /**
   * Definition for a binary tree node.
   * public class TreeNode {
   *     int val;
   *     TreeNode left;
   *     TreeNode right;
   *     TreeNode() {}
   *     TreeNode(int val) { this.val = val; }
   *     TreeNode(int val, TreeNode left, TreeNode right) {
   *         this.val = val;
   *         this.left = left;
   *         this.right = right;
   *     }
   * }
   */
  class Solution {
      public TreeNode convertBST(TreeNode root) {
          int s = 0;
          TreeNode node = root;
          while (root != null) {
              if (root.right == null) {
                  s += root.val;
                  root.val = s;
                  root = root.left;
              } else {
                  TreeNode next = root.right;
                  while (next.left != null && next.left != root) {
                      next = next.left;
                  }
                  if (next.left == null) {
                      next.left = root;
                      root = root.right;
                  } else {
                      s += root.val;
                      root.val = s;
                      next.left = null;
                      root = root.left;
                  }
              }
          }
          return node;
      }
  }
  

• // OJ: https://leetcode.com/problems/convert-bst-to-greater-tree/
  // Time: O(N)
  // Space: O(H)
  class Solution {
      int sum = 0;
  public:
      TreeNode* convertBST(TreeNode* root) {
          if (!root) return nullptr;
          convertBST(root->right);
          root->val = (sum += root->val);
          convertBST(root->left);
          return root;
      }
  };
  

• # Definition for a binary tree node.
  # class TreeNode:
  #     def __init__(self, val=0, left=None, right=None):
  #         self.val = val
  #         self.left = left
  #         self.right = right
  
  # same but just left/right mirror of https://leetcode.ca/2016-03-03-94-Binary-Tree-Inorder-Traversal/
  class Solution:
      def convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
          stack = []
          current = root
          s = 0 # sum
          while stack or current:
              while current:
                  stack.append(current)
                  current = current.right
  
              right_or_middle = stack.pop()
              s += right_or_middle.val
              right_or_middle.val = s
  
              current = right_or_middle.left
  
          return root
  
  ############
  
  # Definition for a binary tree node.
  # class TreeNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.left = None
  #         self.right = None
  
  class Solution(object):
    def __init__(self):
      self.lSum = 0
  
    def convertBST(self, root):
      """
      :type root: TreeNode
      :rtype: TreeNode
      """
      if not root:
        return None
      self.convertBST(root.right)
      self.lSum += root.val
      root.val = self.lSum
      self.convertBST(root.left)
      return root
  
  

• /**
   * Definition for a binary tree node.
   * type TreeNode struct {
   *     Val int
   *     Left *TreeNode
   *     Right *TreeNode
   * }
   */
  func convertBST(root *TreeNode) *TreeNode {
  	s := 0
  	node := root
  	for root != nil {
  		if root.Right == nil {
  			s += root.Val
  			root.Val = s
  			root = root.Left
  		} else {
  			next := root.Right
  			for next.Left != nil && next.Left != root {
  				next = next.Left
  			}
  			if next.Left == nil {
  				next.Left = root
  				root = root.Right
  			} else {
  				s += root.Val
  				root.Val = s
  				next.Left = nil
  				root = root.Left
  			}
  		}
  	}
  	return node
  }
  

All Problems

All Solutions