Coverage for blog/dsa/leetcode/bt/inorder/__init__.py: 65%

1from typing import Any, Iterator 

2 

3import pytest 

4 

5from dsa.leetcode.bt.from_desc import TreeNode 

6 

7 

8# start snippet solution_trivial 

9class SolutionTrivial: 

10 def _inorderTraversal(self, root: TreeNode) -> Iterator[int]: 

11 

12 if root.left is not None: 

13 yield from self._inorderTraversal(root.left) 

14 yield root.val 

15 if root.right is not None: 

16 yield from self._inorderTraversal(root.right) 

17 

18 def inorderTraversal(self, root: TreeNode | None) -> list[int]: 

19 if root is None: 

20 return list() 

21 

22 return list(self._inorderTraversal(root)) 

23 

24 # end snippet solution_trivial 

25 

26 

27# start snippet solution_trivial_improved 

28class SolutionTrivial2: 

29 def _inorderTraversal(self, root: TreeNode, nodes: list[int]): 

30 

31 if root.left is not None: 

32 self._inorderTraversal(root.left, nodes) 

33 

34 nodes.append(root.val) 

35 

36 if root.right is not None: 

37 self._inorderTraversal(root.right, nodes) 

38 

39 def inorderTraversal(self, root: TreeNode | None) -> list[int]: 

40 vals: list[int] = list() 

41 if root is None: 

42 return vals 

43 

44 self._inorderTraversal(root, vals) 

45 return vals 

46 

47 # end snippet solution_trivial_improved 

48 

49 

50# start snippet solution_nontrivial 

51class Solution: 

52 def _inorderTraversal(self, root: TreeNode): 

53 

54 stack: list[TreeNode] = [] 

55 node: TreeNode | None = root 

56 while stack or node is not None: 

57 # If left is found, keep going left 

58 while node is not None: 

59 stack.append(node) 

60 node = node.left 

61 

62 # When no left is found, yield value. Node is ``None`` so use the 

63 # top of the stack. 

64 node = stack.pop() 

65 yield node.val 

66 

67 # Now that the top of the stack has been used, this will be added 

68 # to the stack in the nested ``while`` loop. 

69 node = node.right 

70 

71 def inorderTraversal(self, root: TreeNode | None): 

72 if root is None: 

73 return list() 

74 

75 return list(self._inorderTraversal(root)) 

76 

77 # end snippet solution_nontrivial 

78 

79 

80@pytest.fixture 

81def solution(): 

82 return Solution() 

83 

84 

85@pytest.mark.parametrize( 

86 "tree, answer", 

87 ( 

88 ({"value": 1, "right": {"value": 2, "left": 3}}, [1, 3, 2]), 

89 ( 

90 { 

91 "value": 1, 

92 "left": { 

93 "value": 2, 

94 "left": 4, 

95 "right": {"value": 5, "left": 6, "right": 7}, 

96 }, 

97 "right": { 

98 "value": 3, 

99 "right": { 

100 "value": 8, 

101 "left": 9, 

102 }, 

103 }, 

104 }, 

105 [4, 2, 6, 5, 7, 1, 3, 9, 8], 

106 ), 

107 ({"value": 1}, [1]), 

108 (None, []), 

109 ), 

110) 

111def test_solution(solution: Solution, tree: dict[str, Any], answer: list[int]): 

112 

113 root = TreeNode.fromDict(tree) 

114 answer_computed = solution.inorderTraversal(root) 

115 print(answer_computed) 

116 print(answer) 

117 assert answer == answer_computed