FilesExpand file tree

 master

/

binary-search-tree-iterator.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

64 lines (56 loc) · 1.99 KB

 master

/

binary-search-tree-iterator.java

Copy path

Top

File metadata and controls

• Code
• Blame

64 lines (56 loc) · 1.99 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

/// Morris traversal: O(1) space.

public class Solution {

//@param root: The root of binary tree.

TreeNode runner = null;

public Solution(TreeNode root) {

// write your code here

runner = root;

}

//@return: True if there has next node, or false

public boolean hasNext() {

// write your code here

// using morris traversal we make sure

// runner pointer will always not be null

// untill traversal is done.

return runner != null;

}

//@return: return next node

public TreeNode next() {

// first check left subtree, if null then we visit

// current node and move to its right subtree.

if (runner.left == null) {

// visit runner

TreeNode res = runner;

runner = runner.right;

return res;

} else {

// if left subtree not null, means we either

// havent visit the substree or current node.

//

// first while loop continues untill we find next

// in-order element.

while (runner.left != null) {

// check whether predecessor's right pointer

// points to current node.

TreeNode pre = runner.left;

while (pre.right != null && pre.right != runner) {

pre = pre.right;

}

if (pre.right == runner) {

// already visited left subtree. visit current node.

pre.right = null;

TreeNode res = runner;

runner = runner.right;

return res;

} else {

// visit left subtree first.

pre.right = runner;

runner = runner.left;

}

}

TreeNode res = runner;

runner = runner.right;

return res;

}

}

}