Traverse the binary tree in left → root → right order using recursion. For each node, recurse into the left subtree first, then record the current node's value, and finally recurse into the right subtree.
Use an explicit stack to simulate the recursive call stack. Push nodes onto the stack while traversing left. When there are no more left children, pop from the stack, record the value, and move to the right child.
""" 0094.1 - Solution 1 - Recursive DFS """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""Inorder Traversal Function"""
def dfs(node):
if node is None:
return
dfs(node.left)
ans.append(node.val)
dfs(node.right)
ans = []
dfs(root)
return ans
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Tree: [1, null, 2, 3] -> Expected: [1, 3, 2]
root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(Solution().inorderTraversal(root1))
# Tree: [] -> Expected: []
print(Solution().inorderTraversal(None))
# Tree: [1] -> Expected: [1]
root3 = TreeNode(1)
print(Solution().inorderTraversal(root3))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()
""" 0094.2 - Solution 2 - Iterative with Stack """
#####################################################################################
# Imports
#####################################################################################
from typing import List, Optional
#####################################################################################
# Classes
#####################################################################################
class TreeNode:
"""TreeNode Class"""
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
"""Solution Class"""
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
"""Inorder Traversal Function"""
ans = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
ans.append(current.val)
current = current.right
return ans
#####################################################################################
# Functions
#####################################################################################
def testcase():
"""Test Function"""
# Tree: [1, null, 2, 3] -> Expected: [1, 3, 2]
root1 = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(Solution().inorderTraversal(root1))
# Tree: [] -> Expected: []
print(Solution().inorderTraversal(None))
# Tree: [1] -> Expected: [1]
root3 = TreeNode(1)
print(Solution().inorderTraversal(root3))
#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
testcase()