FilesExpand file tree

 master

/

RecoverBinarySearchTree.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

88 lines (82 loc) · 2.02 KB

 master

/

RecoverBinarySearchTree.java

Copy path

Top

File metadata and controls

• Code
• Blame

88 lines (82 loc) · 2.02 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

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

package tree;

/**

* Created by gouthamvidyapradhan on 28/07/2018. Two elements of a binary search tree (BST) are

* swapped by mistake.

*

* <p>Recover the tree without changing its structure.

*

* <p>Example 1:

*

* <p>Input: [1,3,null,null,2]

*

* <p>1 / 3 \ 2

*

* <p>Output: [3,1,null,null,2]

*

* <p>3 / 1 \ 2 Example 2:

*

* <p>Input: [3,1,4,null,null,2]

*

* <p>3 / \ 1 4 / 2

*

* <p>Output: [2,1,4,null,null,3]

*

* <p>2 / \ 1 4 / 3 Follow up:

*

* <p>A solution using O(n) space is pretty straight forward. Could you devise a constant space

* solution?

*

* <p>Solution: O(N) time and O(1) space. Step 1, perform a inorder traversal and mark left and

* right pointer at the node where violation of BST occurs. Step2, find the next node which is

* smaller or equal to right pointer node. Finally swap left and right node values.

*/

public class RecoverBinarySearchTree {

private boolean violation;

private TreeNode left, right, prev;

public static class TreeNode {

int val;

TreeNode left;

TreeNode right;

TreeNode(int x) {

val = x;

}

}

public static void main(String[] args) throws Exception {

TreeNode root = new TreeNode(10);

root.left = new TreeNode(1);

root.left.left = new TreeNode(3);

root.left.left.left = new TreeNode(5);

new RecoverBinarySearchTree().recoverTree(root);

}

public void recoverTree(TreeNode root) {

inorder(root);

if (left != null && right != null) {

int temp = left.val;

left.val = right.val;

right.val = temp;

}

}

private void inorder(TreeNode root) {

if (root != null) {

inorder(root.left);

if (prev != null) {

if (!violation) {

if (prev.val > root.val) {

violation = true;

left = prev;

right = root;

} else {

prev = root;

}

} else {

if (root.val <= right.val) {

right = root;

}

}

} else {

prev = root;

}

inorder(root.right);

}

}

}