FilesExpand file tree

 master

/

ConvertBSTToGreaterTree.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

54 lines (49 loc) · 1.42 KB

 master

/

ConvertBSTToGreaterTree.java

Top

File metadata and controls

• Code
• Blame

54 lines (49 loc) · 1.42 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

package tree;

/**

* Created by gouthamvidyapradhan on 14/03/2019

* 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

*/

public class ConvertBSTToGreaterTree {

public static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) { val = x; }

}

/**

* Main method

* @param args

*/

public static void main(String[] args) {

TreeNode node = new TreeNode(5);

node.right = new TreeNode(13);

node.left = new TreeNode(2);

node.left.left = new TreeNode(1);

node.left.right = new TreeNode(3);

TreeNode result = new ConvertBSTToGreaterTree().convertBST(node);

System.out.println(result);

}

public TreeNode convertBST(TreeNode root) {

postOrder(root, 0);

return root;

}

private int postOrder(TreeNode node, int value){

if(node == null) return value;

int right = postOrder(node.right, value);

node.val = node.val + right;

return postOrder(node.left, node.val);

}

}