FilesExpand file tree

 master

/

TreeTraversal.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

121 lines (109 loc) · 3.07 KB

 master

/

TreeTraversal.java

Top

File metadata and controls

• Code
• Blame

121 lines (109 loc) · 3.07 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

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

package DataStructures.Trees;

import java.util.LinkedList;

/**

* @author Varun Upadhyay (https://github.com/varunu28)

*/

// Driver Program

public class TreeTraversal {

public static void main(String[] args) {

Node tree = new Node(5);

tree.insert(3);

tree.insert(2);

tree.insert(7);

tree.insert(4);

tree.insert(6);

tree.insert(8);

// Prints 5 3 2 4 7 6 8

System.out.println("Pre order traversal:");

tree.printPreOrder();

System.out.println();

// Prints 2 3 4 5 6 7 8

System.out.println("In order traversal:");

tree.printInOrder();

System.out.println();

// Prints 2 4 3 6 8 7 5

System.out.println("Post order traversal:");

tree.printPostOrder();

System.out.println();

// Prints 5 3 7 2 4 6 8

System.out.println("Level order traversal:");

tree.printLevelOrder();

System.out.println();

}

}

/**

* The Node class which initializes a Node of a tree

* Consists of all 4 traversal methods: printInOrder, printPostOrder， printPreOrder & printLevelOrder

* printInOrder: LEFT -> ROOT -> RIGHT

* printPreOrder: ROOT -> LEFT -> RIGHT

* printPostOrder: LEFT -> RIGHT -> ROOT

* printLevelOrder: Prints by level (starting at root), from left to right.

*/

class Node {

Node left, right;

int data;

public Node(int data) {

this.data = data;

}

public void insert(int value) {

if (value < data) {

if (left == null) {

left = new Node(value);

} else {

left.insert(value);

}

} else {

if (right == null) {

right = new Node(value);

} else {

right.insert(value);

}

}

}

public void printInOrder() {

if (left != null) {

left.printInOrder();

}

System.out.print(data + " ");

if (right != null) {

right.printInOrder();

}

}

public void printPreOrder() {

System.out.print(data + " ");

if (left != null) {

left.printPreOrder();

}

if (right != null) {

right.printPreOrder();

}

}

public void printPostOrder() {

if (left != null) {

left.printPostOrder();

}

if (right != null) {

right.printPostOrder();

}

System.out.print(data + " ");

}

/**

* O(n) time algorithm.

* Uses O(n) space to store nodes in a queue to aid in traversal.

*/

public void printLevelOrder() {

LinkedList<Node> queue = new LinkedList<>();

queue.add(this);

while (queue.size() > 0) {

Node head = queue.remove();

System.out.print(head.data + " ");

// Add children of recently-printed node to queue, if they exist.

if (head.left != null) {

queue.add(head.left);

}

if (head.right != null) {

queue.add(head.right);

}

}

}

}