Coverage for blog/dsa/leetcode/bt/inorder/__init__.py: 65%
52 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1from typing import Any, Iterator
3import pytest
5from dsa.leetcode.bt.from_desc import TreeNode
8# start snippet solution_trivial
9class SolutionTrivial:
10 def _inorderTraversal(self, root: TreeNode) -> Iterator[int]:
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)
18 def inorderTraversal(self, root: TreeNode | None) -> list[int]:
19 if root is None:
20 return list()
22 return list(self._inorderTraversal(root))
24 # end snippet solution_trivial
27# start snippet solution_trivial_improved
28class SolutionTrivial2:
29 def _inorderTraversal(self, root: TreeNode, nodes: list[int]):
31 if root.left is not None:
32 self._inorderTraversal(root.left, nodes)
34 nodes.append(root.val)
36 if root.right is not None:
37 self._inorderTraversal(root.right, nodes)
39 def inorderTraversal(self, root: TreeNode | None) -> list[int]:
40 vals: list[int] = list()
41 if root is None:
42 return vals
44 self._inorderTraversal(root, vals)
45 return vals
47 # end snippet solution_trivial_improved
50# start snippet solution_nontrivial
51class Solution:
52 def _inorderTraversal(self, root: TreeNode):
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
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
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
71 def inorderTraversal(self, root: TreeNode | None):
72 if root is None:
73 return list()
75 return list(self._inorderTraversal(root))
77 # end snippet solution_nontrivial
80@pytest.fixture
81def solution():
82 return Solution()
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]):
113 root = TreeNode.fromDict(tree)
114 answer_computed = solution.inorderTraversal(root)
115 print(answer_computed)
116 print(answer)
117 assert answer == answer_computed