FilesExpand file tree

 master

/

GrokkingDepthFirstSearch.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

75 lines (63 loc) · 1.74 KB

 master

/

GrokkingDepthFirstSearch.java

Copy path

Top

File metadata and controls

• Code
• Blame

75 lines (63 loc) · 1.74 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

package com.cunningdj.grokJava;

import java.util.Stack;

class GrokkingDepthFirstSearch {

public static void main(String[] args) {

Tester tester = new Tester();

String testTitle="";

// TREE_HEIGHT

testTitle = "TREE_HEIGHT";

TreeNode root = buildTestTree();

tester.intEquals(5, treeHeight(root), testTitle);

root.right.left.left.right.right = new TreeNode(88);

tester.intEquals(6, treeHeight(root), testTitle);

}

public static TreeNode buildTestTree() {

// Builds a sample tree for testing. Returns the tree root

// LEVEL 1

TreeNode root = new TreeNode(1);

// LEVEL 2

root.left = new TreeNode(2);

root.right = new TreeNode(3);

// LEVEL 3

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

root.right.left = new TreeNode(6);

root.right.right = new TreeNode(7);

// LEVEL 4

root.left.left.right = new TreeNode(9);

root.right.left.left = new TreeNode(11);

// LEVEL 5

root.right.left.left.right = new TreeNode(20);

return root;

}

public static int treeHeight(TreeNode root) {

if (root == null) {

return 0;

}

int maxHeight = 0;

Stack<NodeHeightPair> st = new Stack<>();

st.push(new NodeHeightPair(root, 1));

NodeHeightPair nhp;

while (st.size() > 0) {

nhp = st.pop();

if (nhp.node.left == null && nhp.node.right == null) {

maxHeight = Math.max(maxHeight, nhp.height);

} else {

if (nhp.node.right != null) {

st.push(new NodeHeightPair(nhp.node.right, nhp.height + 1));

}

if (nhp.node.left != null) {

st.push(new NodeHeightPair(nhp.node.left, nhp.height + 1));

}

}

}

return maxHeight;

}

private static class NodeHeightPair {

TreeNode node;

Integer height;

public NodeHeightPair(TreeNode node, Integer height) {

this.node = node;

this.height = height;

}

}

}