We are currently solving the following issue within our repository. Here is the issue text:
--- BEGIN ISSUE ---
Making binary tree traversals lazy.
### Feature description

Hi,
In [binary_tree_traversals.py](https://github.com/TheAlgorithms/Python/blob/master/data_structures/binary_tree/binary_tree_traversals.py) file, there are different kinds of traversals such as `preorder`, `inorder`, `postorder` and etc.

Although the implementations are pretty clean one-liner like:
```python
# preorder
return [root.data, *preorder(root.left), *preorder(root.right)] if root else []
```
It isn't memory friendly. We can use generators instead not to load all the nodes into the memory:

```python
# preorder
    if not root:
        return []
    yield root.data
    yield from preorder(root.left)
    yield from preorder(root.right)
```
Shall we go ahead and change them?

--- END ISSUE ---

Below are some code segments, each from a relevant file. One or more of these files may contain bugs.
--- BEGIN FILES ---
Path: `data_structures/binary_tree/binary_tree_traversals.py`
Content:
```
1 # https://en.wikipedia.org/wiki/Tree_traversal
2 from __future__ import annotations
3 
4 from collections import deque
5 from collections.abc import Sequence
6 from dataclasses import dataclass
7 from typing import Any
8 
9 
10 @dataclass
11 class Node:
12     data: int
13     left: Node | None = None
14     right: Node | None = None
15 
16 
17 def make_tree() -> Node | None:
18     r"""
19     The below tree
20         1
21        / \
22       2   3
23      / \
24     4   5
25     """
26     tree = Node(1)
27     tree.left = Node(2)
28     tree.right = Node(3)
29     tree.left.left = Node(4)
30     tree.left.right = Node(5)
31     return tree
32 
33 
34 def preorder(root: Node | None) -> list[int]:
35     """
36     Pre-order traversal visits root node, left subtree, right subtree.
37     >>> preorder(make_tree())
38     [1, 2, 4, 5, 3]
39     """
40     return [root.data, *preorder(root.left), *preorder(root.right)] if root else []
41 
42 
43 def postorder(root: Node | None) -> list[int]:
44     """
45     Post-order traversal visits left subtree, right subtree, root node.
46     >>> postorder(make_tree())
47     [4, 5, 2, 3, 1]
48     """
49     return postorder(root.left) + postorder(root.right) + [root.data] if root else []
50 
51 
52 def inorder(root: Node | None) -> list[int]:
53     """
54     In-order traversal visits left subtree, root node, right subtree.
55     >>> inorder(make_tree())
56     [4, 2, 5, 1, 3]
57     """
58     return [*inorder(root.left), root.data, *inorder(root.right)] if root else []
59 
60 
61 def reverse_inorder(root: Node | None) -> list[int]:
62     """
63     Reverse in-order traversal visits right subtree, root node, left subtree.
64     >>> reverse_inorder(make_tree())
65     [3, 1, 5, 2, 4]
66     """
67     return (
68         [*reverse_inorder(root.right), root.data, *reverse_inorder(root.left)]
69         if root
70         else []
71     )
72 
73 
74 def height(root: Node | None) -> int:
75     """
76     Recursive function for calculating the height of the binary tree.
77     >>> height(None)
78     0
79     >>> height(make_tree())
80     3
81     """
82     return (max(height(root.left), height(root.right)) + 1) if root else 0
83 
84 
85 def level_order(root: Node | None) -> Sequence[Node | None]:
86     """
87     Returns a list of nodes value from a whole binary tree in Level Order Traverse.
88     Level Order traverse: Visit nodes of the tree level-by-level.
89     """
90     output: list[Any] = []
91 
92     if root is None:
93         return output
94 
95     process_queue = deque([root])
96 
97     while process_queue:
98         node = process_queue.popleft()
99         output.append(node.data)
100 
101         if node.left:
102             process_queue.append(node.left)
103         if node.right:
104             process_queue.append(node.right)
105     return output
106 
107 
108 def get_nodes_from_left_to_right(
109     root: Node | None, level: int
110 ) -> Sequence[Node | None]:
111     """
112     Returns a list of nodes value from a particular level:
113     Left to right direction of the binary tree.
114     """
115     output: list[Any] = []
116 
117     def populate_output(root: Node | None, level: int) -> None:
118         if not root:
119             return
120         if level == 1:
121             output.append(root.data)
122         elif level > 1:
123             populate_output(root.left, level - 1)
124             populate_output(root.right, level - 1)
125 
126     populate_output(root, level)
127     return output
128 
129 
130 def get_nodes_from_right_to_left(
131     root: Node | None, level: int
132 ) -> Sequence[Node | None]:
133     """
134     Returns a list of nodes value from a particular level:
135     Right to left direction of the binary tree.
136     """
137     output: list[Any] = []
138 
139     def populate_output(root: Node | None, level: int) -> None:
140         if root is None:
141             return
142         if level == 1:
143             output.append(root.data)
144         elif level > 1:
145             populate_output(root.right, level - 1)
146             populate_output(root.left, level - 1)
147 
148     populate_output(root, level)
149     return output
150 
151 
152 def zigzag(root: Node | None) -> Sequence[Node | None] | list[Any]:
153     """
154     ZigZag traverse:
155     Returns a list of nodes value from left to right and right to left, alternatively.
156     """
157     if root is None:
158         return []
159 
160     output: list[Sequence[Node | None]] = []
161 
162     flag = 0
163     height_tree = height(root)
164 
165     for h in range(1, height_tree + 1):
166         if not flag:
167             output.append(get_nodes_from_left_to_right(root, h))
168             flag = 1
169         else:
170             output.append(get_nodes_from_right_to_left(root, h))
171             flag = 0
172 
173     return output
174 
175 
176 def main() -> None:  # Main function for testing.
177     # Create binary tree.
178     root = make_tree()
179 
180     # All Traversals of the binary are as follows:
181     print(f"In-order Traversal: {inorder(root)}")
182     print(f"Reverse In-order Traversal: {reverse_inorder(root)}")
183     print(f"Pre-order Traversal: {preorder(root)}")
184     print(f"Post-order Traversal: {postorder(root)}", "\n")
185 
186     print(f"Height of Tree: {height(root)}", "\n")
187 
188     print("Complete Level Order Traversal: ")
189     print(level_order(root), "\n")
190 
191     print("Level-wise order Traversal: ")
192 
193     for level in range(1, height(root) + 1):
194         print(f"Level {level}:", get_nodes_from_left_to_right(root, level=level))
195 
196     print("\nZigZag order Traversal: ")
197     print(zigzag(root))
198 
199 
200 if __name__ == "__main__":
201     import doctest
202 
203     doctest.testmod()
204     main()
205
```
--- END FILES ---

Please first localize the bug based on the issue statement, and then generate a patch according to the `git diff` format fenced by three backticks.

Here is an example:

```diff
diff --git a/examples/server_async.py b/examples/server_async.py
--- a/examples/server_async.py
+++ b/examples/server_async.py
@@ -313,4 +313,4 @@
 
 
 if __name__ == "__main__":
-    asyncio.run(run_async_server("."), debug=True)
+    asyncio.run(run_async_server(), debug=True)
diff --git a/examples/server_sync.py b/examples/server_sync.py
--- a/examples/server_sync.py
+++ b/examples/server_sync.py
@@ -313,5 +313,5 @@
 
 
 if __name__ == "__main__":
-    server = run_sync_server(".")
+    server = run_sync_server()
     server.shutdown()

```

diff --git a/data_structures/binary_tree/binary_tree_traversals.py b/data_structures/binary_tree/binary_tree_traversals.py
--- a/data_structures/binary_tree/binary_tree_traversals.py
+++ b/data_structures/binary_tree/binary_tree_traversals.py
@@ -1,12 +1,12 @@
-# https://en.wikipedia.org/wiki/Tree_traversal
 from __future__ import annotations
 
 from collections import deque
-from collections.abc import Sequence
+from collections.abc import Generator, Sequence
 from dataclasses import dataclass
 from typing import Any
 
 
+# https://en.wikipedia.org/wiki/Tree_traversal
 @dataclass
 class Node:
     data: int
@@ -31,44 +31,56 @@
     return tree
 
 
-def preorder(root: Node | None) -> list[int]:
+def preorder(root: Node | None) -> Generator[int, None, None]:
     """
     Pre-order traversal visits root node, left subtree, right subtree.
-    >>> preorder(make_tree())
+    >>> list(preorder(make_tree()))
     [1, 2, 4, 5, 3]
     """
-    return [root.data, *preorder(root.left), *preorder(root.right)] if root else []
+    if not root:
+        return
+    yield root.data
+    yield from preorder(root.left)
+    yield from preorder(root.right)
 
 
-def postorder(root: Node | None) -> list[int]:
+def postorder(root: Node | None) -> Generator[int, None, None]:
     """
     Post-order traversal visits left subtree, right subtree, root node.
-    >>> postorder(make_tree())
+    >>> list(postorder(make_tree()))
     [4, 5, 2, 3, 1]
     """
-    return postorder(root.left) + postorder(root.right) + [root.data] if root else []
+    if not root:
+        return
+    yield from postorder(root.left)
+    yield from postorder(root.right)
+    yield root.data
 
 
-def inorder(root: Node | None) -> list[int]:
+def inorder(root: Node | None) -> Generator[int, None, None]:
     """
     In-order traversal visits left subtree, root node, right subtree.
-    >>> inorder(make_tree())
+    >>> list(inorder(make_tree()))
     [4, 2, 5, 1, 3]
     """
-    return [*inorder(root.left), root.data, *inorder(root.right)] if root else []
+    if not root:
+        return
+    yield from inorder(root.left)
+    yield root.data
+    yield from inorder(root.right)
 
 
-def reverse_inorder(root: Node | None) -> list[int]:
+def reverse_inorder(root: Node | None) -> Generator[int, None, None]:
     """
     Reverse in-order traversal visits right subtree, root node, left subtree.
-    >>> reverse_inorder(make_tree())
+    >>> list(reverse_inorder(make_tree()))
     [3, 1, 5, 2, 4]
     """
-    return (
-        [*reverse_inorder(root.right), root.data, *reverse_inorder(root.left)]
-        if root
-        else []
-    )
+    if not root:
+        return
+    yield from reverse_inorder(root.right)
+    yield root.data
+    yield from reverse_inorder(root.left)
 
 
 def height(root: Node | None) -> int:
@@ -178,10 +190,10 @@
     root = make_tree()
 
     # All Traversals of the binary are as follows:
-    print(f"In-order Traversal: {inorder(root)}")
-    print(f"Reverse In-order Traversal: {reverse_inorder(root)}")
-    print(f"Pre-order Traversal: {preorder(root)}")
-    print(f"Post-order Traversal: {postorder(root)}", "\n")
+    print(f"In-order Traversal: {list(inorder(root))}")
+    print(f"Reverse In-order Traversal: {list(reverse_inorder(root))}")
+    print(f"Pre-order Traversal: {list(preorder(root))}")
+    print(f"Post-order Traversal: {list(postorder(root))}", "\n")
 
     print(f"Height of Tree: {height(root)}", "\n")

{"golden_diff": "diff --git a/data_structures/binary_tree/binary_tree_traversals.py b/data_structures/binary_tree/binary_tree_traversals.py\n--- a/data_structures/binary_tree/binary_tree_traversals.py\n+++ b/data_structures/binary_tree/binary_tree_traversals.py\n@@ -1,12 +1,12 @@\n-# https://en.wikipedia.org/wiki/Tree_traversal\r\n from __future__ import annotations\r\n \r\n from collections import deque\r\n-from collections.abc import Sequence\r\n+from collections.abc import Generator, Sequence\r\n from dataclasses import dataclass\r\n from typing import Any\r\n \r\n \r\n+# https://en.wikipedia.org/wiki/Tree_traversal\r\n @dataclass\r\n class Node:\r\n     data: int\r\n@@ -31,44 +31,56 @@\n     return tree\r\n \r\n \r\n-def preorder(root: Node | None) -> list[int]:\r\n+def preorder(root: Node | None) -> Generator[int, None, None]:\r\n     \"\"\"\r\n     Pre-order traversal visits root node, left subtree, right subtree.\r\n-    >>> preorder(make_tree())\r\n+    >>> list(preorder(make_tree()))\r\n     [1, 2, 4, 5, 3]\r\n     \"\"\"\r\n-    return [root.data, *preorder(root.left), *preorder(root.right)] if root else []\r\n+    if not root:\r\n+        return\r\n+    yield root.data\r\n+    yield from preorder(root.left)\r\n+    yield from preorder(root.right)\r\n \r\n \r\n-def postorder(root: Node | None) -> list[int]:\r\n+def postorder(root: Node | None) -> Generator[int, None, None]:\r\n     \"\"\"\r\n     Post-order traversal visits left subtree, right subtree, root node.\r\n-    >>> postorder(make_tree())\r\n+    >>> list(postorder(make_tree()))\r\n     [4, 5, 2, 3, 1]\r\n     \"\"\"\r\n-    return postorder(root.left) + postorder(root.right) + [root.data] if root else []\r\n+    if not root:\r\n+        return\r\n+    yield from postorder(root.left)\r\n+    yield from postorder(root.right)\r\n+    yield root.data\r\n \r\n \r\n-def inorder(root: Node | None) -> list[int]:\r\n+def inorder(root: Node | None) -> Generator[int, None, None]:\r\n     \"\"\"\r\n     In-order traversal visits left subtree, root node, right subtree.\r\n-    >>> inorder(make_tree())\r\n+    >>> list(inorder(make_tree()))\r\n     [4, 2, 5, 1, 3]\r\n     \"\"\"\r\n-    return [*inorder(root.left), root.data, *inorder(root.right)] if root else []\r\n+    if not root:\r\n+        return\r\n+    yield from inorder(root.left)\r\n+    yield root.data\r\n+    yield from inorder(root.right)\r\n \r\n \r\n-def reverse_inorder(root: Node | None) -> list[int]:\r\n+def reverse_inorder(root: Node | None) -> Generator[int, None, None]:\r\n     \"\"\"\r\n     Reverse in-order traversal visits right subtree, root node, left subtree.\r\n-    >>> reverse_inorder(make_tree())\r\n+    >>> list(reverse_inorder(make_tree()))\r\n     [3, 1, 5, 2, 4]\r\n     \"\"\"\r\n-    return (\r\n-        [*reverse_inorder(root.right), root.data, *reverse_inorder(root.left)]\r\n-        if root\r\n-        else []\r\n-    )\r\n+    if not root:\r\n+        return\r\n+    yield from reverse_inorder(root.right)\r\n+    yield root.data\r\n+    yield from reverse_inorder(root.left)\r\n \r\n \r\n def height(root: Node | None) -> int:\r\n@@ -178,10 +190,10 @@\n     root = make_tree()\r\n \r\n     # All Traversals of the binary are as follows:\r\n-    print(f\"In-order Traversal: {inorder(root)}\")\r\n-    print(f\"Reverse In-order Traversal: {reverse_inorder(root)}\")\r\n-    print(f\"Pre-order Traversal: {preorder(root)}\")\r\n-    print(f\"Post-order Traversal: {postorder(root)}\", \"\\n\")\r\n+    print(f\"In-order Traversal: {list(inorder(root))}\")\r\n+    print(f\"Reverse In-order Traversal: {list(reverse_inorder(root))}\")\r\n+    print(f\"Pre-order Traversal: {list(preorder(root))}\")\r\n+    print(f\"Post-order Traversal: {list(postorder(root))}\", \"\\n\")\r\n \r\n     print(f\"Height of Tree: {height(root)}\", \"\\n\")\n", "issue": "Making binary tree traversals lazy.\n### Feature description\n\nHi,\r\nIn [binary_tree_traversals.py](https://github.com/TheAlgorithms/Python/blob/master/data_structures/binary_tree/binary_tree_traversals.py) file, there are different kinds of traversals such as `preorder`, `inorder`, `postorder` and etc.\r\n\r\nAlthough the implementations are pretty clean one-liner like:\r\n```python\r\n# preorder\r\nreturn [root.data, *preorder(root.left), *preorder(root.right)] if root else []\r\n```\r\nIt isn't memory friendly. We can use generators instead not to load all the nodes into the memory:\r\n\r\n```python\r\n# preorder\r\n    if not root:\r\n        return []\r\n    yield root.data\r\n    yield from preorder(root.left)\r\n    yield from preorder(root.right)\r\n```\r\nShall we go ahead and change them?\n", "before_files": [{"content": "# https://en.wikipedia.org/wiki/Tree_traversal\r\nfrom __future__ import annotations\r\n\r\nfrom collections import deque\r\nfrom collections.abc import Sequence\r\nfrom dataclasses import dataclass\r\nfrom typing import Any\r\n\r\n\r\n@dataclass\r\nclass Node:\r\n    data: int\r\n    left: Node | None = None\r\n    right: Node | None = None\r\n\r\n\r\ndef make_tree() -> Node | None:\r\n    r\"\"\"\r\n    The below tree\r\n        1\r\n       / \\\r\n      2   3\r\n     / \\\r\n    4   5\r\n    \"\"\"\r\n    tree = Node(1)\r\n    tree.left = Node(2)\r\n    tree.right = Node(3)\r\n    tree.left.left = Node(4)\r\n    tree.left.right = Node(5)\r\n    return tree\r\n\r\n\r\ndef preorder(root: Node | None) -> list[int]:\r\n    \"\"\"\r\n    Pre-order traversal visits root node, left subtree, right subtree.\r\n    >>> preorder(make_tree())\r\n    [1, 2, 4, 5, 3]\r\n    \"\"\"\r\n    return [root.data, *preorder(root.left), *preorder(root.right)] if root else []\r\n\r\n\r\ndef postorder(root: Node | None) -> list[int]:\r\n    \"\"\"\r\n    Post-order traversal visits left subtree, right subtree, root node.\r\n    >>> postorder(make_tree())\r\n    [4, 5, 2, 3, 1]\r\n    \"\"\"\r\n    return postorder(root.left) + postorder(root.right) + [root.data] if root else []\r\n\r\n\r\ndef inorder(root: Node | None) -> list[int]:\r\n    \"\"\"\r\n    In-order traversal visits left subtree, root node, right subtree.\r\n    >>> inorder(make_tree())\r\n    [4, 2, 5, 1, 3]\r\n    \"\"\"\r\n    return [*inorder(root.left), root.data, *inorder(root.right)] if root else []\r\n\r\n\r\ndef reverse_inorder(root: Node | None) -> list[int]:\r\n    \"\"\"\r\n    Reverse in-order traversal visits right subtree, root node, left subtree.\r\n    >>> reverse_inorder(make_tree())\r\n    [3, 1, 5, 2, 4]\r\n    \"\"\"\r\n    return (\r\n        [*reverse_inorder(root.right), root.data, *reverse_inorder(root.left)]\r\n        if root\r\n        else []\r\n    )\r\n\r\n\r\ndef height(root: Node | None) -> int:\r\n    \"\"\"\r\n    Recursive function for calculating the height of the binary tree.\r\n    >>> height(None)\r\n    0\r\n    >>> height(make_tree())\r\n    3\r\n    \"\"\"\r\n    return (max(height(root.left), height(root.right)) + 1) if root else 0\r\n\r\n\r\ndef level_order(root: Node | None) -> Sequence[Node | None]:\r\n    \"\"\"\r\n    Returns a list of nodes value from a whole binary tree in Level Order Traverse.\r\n    Level Order traverse: Visit nodes of the tree level-by-level.\r\n    \"\"\"\r\n    output: list[Any] = []\r\n\r\n    if root is None:\r\n        return output\r\n\r\n    process_queue = deque([root])\r\n\r\n    while process_queue:\r\n        node = process_queue.popleft()\r\n        output.append(node.data)\r\n\r\n        if node.left:\r\n            process_queue.append(node.left)\r\n        if node.right:\r\n            process_queue.append(node.right)\r\n    return output\r\n\r\n\r\ndef get_nodes_from_left_to_right(\r\n    root: Node | None, level: int\r\n) -> Sequence[Node | None]:\r\n    \"\"\"\r\n    Returns a list of nodes value from a particular level:\r\n    Left to right direction of the binary tree.\r\n    \"\"\"\r\n    output: list[Any] = []\r\n\r\n    def populate_output(root: Node | None, level: int) -> None:\r\n        if not root:\r\n            return\r\n        if level == 1:\r\n            output.append(root.data)\r\n        elif level > 1:\r\n            populate_output(root.left, level - 1)\r\n            populate_output(root.right, level - 1)\r\n\r\n    populate_output(root, level)\r\n    return output\r\n\r\n\r\ndef get_nodes_from_right_to_left(\r\n    root: Node | None, level: int\r\n) -> Sequence[Node | None]:\r\n    \"\"\"\r\n    Returns a list of nodes value from a particular level:\r\n    Right to left direction of the binary tree.\r\n    \"\"\"\r\n    output: list[Any] = []\r\n\r\n    def populate_output(root: Node | None, level: int) -> None:\r\n        if root is None:\r\n            return\r\n        if level == 1:\r\n            output.append(root.data)\r\n        elif level > 1:\r\n            populate_output(root.right, level - 1)\r\n            populate_output(root.left, level - 1)\r\n\r\n    populate_output(root, level)\r\n    return output\r\n\r\n\r\ndef zigzag(root: Node | None) -> Sequence[Node | None] | list[Any]:\r\n    \"\"\"\r\n    ZigZag traverse:\r\n    Returns a list of nodes value from left to right and right to left, alternatively.\r\n    \"\"\"\r\n    if root is None:\r\n        return []\r\n\r\n    output: list[Sequence[Node | None]] = []\r\n\r\n    flag = 0\r\n    height_tree = height(root)\r\n\r\n    for h in range(1, height_tree + 1):\r\n        if not flag:\r\n            output.append(get_nodes_from_left_to_right(root, h))\r\n            flag = 1\r\n        else:\r\n            output.append(get_nodes_from_right_to_left(root, h))\r\n            flag = 0\r\n\r\n    return output\r\n\r\n\r\ndef main() -> None:  # Main function for testing.\r\n    # Create binary tree.\r\n    root = make_tree()\r\n\r\n    # All Traversals of the binary are as follows:\r\n    print(f\"In-order Traversal: {inorder(root)}\")\r\n    print(f\"Reverse In-order Traversal: {reverse_inorder(root)}\")\r\n    print(f\"Pre-order Traversal: {preorder(root)}\")\r\n    print(f\"Post-order Traversal: {postorder(root)}\", \"\\n\")\r\n\r\n    print(f\"Height of Tree: {height(root)}\", \"\\n\")\r\n\r\n    print(\"Complete Level Order Traversal: \")\r\n    print(level_order(root), \"\\n\")\r\n\r\n    print(\"Level-wise order Traversal: \")\r\n\r\n    for level in range(1, height(root) + 1):\r\n        print(f\"Level {level}:\", get_nodes_from_left_to_right(root, level=level))\r\n\r\n    print(\"\\nZigZag order Traversal: \")\r\n    print(zigzag(root))\r\n\r\n\r\nif __name__ == \"__main__\":\r\n    import doctest\r\n\r\n    doctest.testmod()\r\n    main()\r\n", "path": "data_structures/binary_tree/binary_tree_traversals.py"}], "after_files": [{"content": "from __future__ import annotations\r\n\r\nfrom collections import deque\r\nfrom collections.abc import Generator, Sequence\r\nfrom dataclasses import dataclass\r\nfrom typing import Any\r\n\r\n\r\n# https://en.wikipedia.org/wiki/Tree_traversal\r\n@dataclass\r\nclass Node:\r\n    data: int\r\n    left: Node | None = None\r\n    right: Node | None = None\r\n\r\n\r\ndef make_tree() -> Node | None:\r\n    r\"\"\"\r\n    The below tree\r\n        1\r\n       / \\\r\n      2   3\r\n     / \\\r\n    4   5\r\n    \"\"\"\r\n    tree = Node(1)\r\n    tree.left = Node(2)\r\n    tree.right = Node(3)\r\n    tree.left.left = Node(4)\r\n    tree.left.right = Node(5)\r\n    return tree\r\n\r\n\r\ndef preorder(root: Node | None) -> Generator[int, None, None]:\r\n    \"\"\"\r\n    Pre-order traversal visits root node, left subtree, right subtree.\r\n    >>> list(preorder(make_tree()))\r\n    [1, 2, 4, 5, 3]\r\n    \"\"\"\r\n    if not root:\r\n        return\r\n    yield root.data\r\n    yield from preorder(root.left)\r\n    yield from preorder(root.right)\r\n\r\n\r\ndef postorder(root: Node | None) -> Generator[int, None, None]:\r\n    \"\"\"\r\n    Post-order traversal visits left subtree, right subtree, root node.\r\n    >>> list(postorder(make_tree()))\r\n    [4, 5, 2, 3, 1]\r\n    \"\"\"\r\n    if not root:\r\n        return\r\n    yield from postorder(root.left)\r\n    yield from postorder(root.right)\r\n    yield root.data\r\n\r\n\r\ndef inorder(root: Node | None) -> Generator[int, None, None]:\r\n    \"\"\"\r\n    In-order traversal visits left subtree, root node, right subtree.\r\n    >>> list(inorder(make_tree()))\r\n    [4, 2, 5, 1, 3]\r\n    \"\"\"\r\n    if not root:\r\n        return\r\n    yield from inorder(root.left)\r\n    yield root.data\r\n    yield from inorder(root.right)\r\n\r\n\r\ndef reverse_inorder(root: Node | None) -> Generator[int, None, None]:\r\n    \"\"\"\r\n    Reverse in-order traversal visits right subtree, root node, left subtree.\r\n    >>> list(reverse_inorder(make_tree()))\r\n    [3, 1, 5, 2, 4]\r\n    \"\"\"\r\n    if not root:\r\n        return\r\n    yield from reverse_inorder(root.right)\r\n    yield root.data\r\n    yield from reverse_inorder(root.left)\r\n\r\n\r\ndef height(root: Node | None) -> int:\r\n    \"\"\"\r\n    Recursive function for calculating the height of the binary tree.\r\n    >>> height(None)\r\n    0\r\n    >>> height(make_tree())\r\n    3\r\n    \"\"\"\r\n    return (max(height(root.left), height(root.right)) + 1) if root else 0\r\n\r\n\r\ndef level_order(root: Node | None) -> Sequence[Node | None]:\r\n    \"\"\"\r\n    Returns a list of nodes value from a whole binary tree in Level Order Traverse.\r\n    Level Order traverse: Visit nodes of the tree level-by-level.\r\n    \"\"\"\r\n    output: list[Any] = []\r\n\r\n    if root is None:\r\n        return output\r\n\r\n    process_queue = deque([root])\r\n\r\n    while process_queue:\r\n        node = process_queue.popleft()\r\n        output.append(node.data)\r\n\r\n        if node.left:\r\n            process_queue.append(node.left)\r\n        if node.right:\r\n            process_queue.append(node.right)\r\n    return output\r\n\r\n\r\ndef get_nodes_from_left_to_right(\r\n    root: Node | None, level: int\r\n) -> Sequence[Node | None]:\r\n    \"\"\"\r\n    Returns a list of nodes value from a particular level:\r\n    Left to right direction of the binary tree.\r\n    \"\"\"\r\n    output: list[Any] = []\r\n\r\n    def populate_output(root: Node | None, level: int) -> None:\r\n        if not root:\r\n            return\r\n        if level == 1:\r\n            output.append(root.data)\r\n        elif level > 1:\r\n            populate_output(root.left, level - 1)\r\n            populate_output(root.right, level - 1)\r\n\r\n    populate_output(root, level)\r\n    return output\r\n\r\n\r\ndef get_nodes_from_right_to_left(\r\n    root: Node | None, level: int\r\n) -> Sequence[Node | None]:\r\n    \"\"\"\r\n    Returns a list of nodes value from a particular level:\r\n    Right to left direction of the binary tree.\r\n    \"\"\"\r\n    output: list[Any] = []\r\n\r\n    def populate_output(root: Node | None, level: int) -> None:\r\n        if root is None:\r\n            return\r\n        if level == 1:\r\n            output.append(root.data)\r\n        elif level > 1:\r\n            populate_output(root.right, level - 1)\r\n            populate_output(root.left, level - 1)\r\n\r\n    populate_output(root, level)\r\n    return output\r\n\r\n\r\ndef zigzag(root: Node | None) -> Sequence[Node | None] | list[Any]:\r\n    \"\"\"\r\n    ZigZag traverse:\r\n    Returns a list of nodes value from left to right and right to left, alternatively.\r\n    \"\"\"\r\n    if root is None:\r\n        return []\r\n\r\n    output: list[Sequence[Node | None]] = []\r\n\r\n    flag = 0\r\n    height_tree = height(root)\r\n\r\n    for h in range(1, height_tree + 1):\r\n        if not flag:\r\n            output.append(get_nodes_from_left_to_right(root, h))\r\n            flag = 1\r\n        else:\r\n            output.append(get_nodes_from_right_to_left(root, h))\r\n            flag = 0\r\n\r\n    return output\r\n\r\n\r\ndef main() -> None:  # Main function for testing.\r\n    # Create binary tree.\r\n    root = make_tree()\r\n\r\n    # All Traversals of the binary are as follows:\r\n    print(f\"In-order Traversal: {list(inorder(root))}\")\r\n    print(f\"Reverse In-order Traversal: {list(reverse_inorder(root))}\")\r\n    print(f\"Pre-order Traversal: {list(preorder(root))}\")\r\n    print(f\"Post-order Traversal: {list(postorder(root))}\", \"\\n\")\r\n\r\n    print(f\"Height of Tree: {height(root)}\", \"\\n\")\r\n\r\n    print(\"Complete Level Order Traversal: \")\r\n    print(level_order(root), \"\\n\")\r\n\r\n    print(\"Level-wise order Traversal: \")\r\n\r\n    for level in range(1, height(root) + 1):\r\n        print(f\"Level {level}:\", get_nodes_from_left_to_right(root, level=level))\r\n\r\n    print(\"\\nZigZag order Traversal: \")\r\n    print(zigzag(root))\r\n\r\n\r\nif __name__ == \"__main__\":\r\n    import doctest\r\n\r\n    doctest.testmod()\r\n    main()\r\n", "path": "data_structures/binary_tree/binary_tree_traversals.py"}]}