To retrieve node values from a binary tree in ascending order (for a BST) or the standard left-root-right sequence, a recursive approach works cleanly. The traversal explores the left subtreee first, records the current node, then visits the right subtree. Below are Python implementations that illustrate this technique.
class TreeNode:
def __init__(self, value=0, left_child=None, right_child=None):
self.value = value
self.left = left_child
self.right = right_child
def traverse_inorder(node, collector):
if node is None:
return
traverse_inorder(node.left, collector)
collector.append(node.value)
traverse_inorder(node.right, collector)
def inorder_values(tree_root):
output = []
traverse_inorder(tree_root, output)
return output
if __name__ == "__main__":
# Build tree: root=1, right->2, right->left->3
sample_tree = TreeNode(1, None, TreeNode(2, TreeNode(3)))
print(inorder_values(sample_tree)) # [1, 3, 2]
An alternative version embeds a nested helper function inside a Solution class:
class Solution:
def inorderTraversal(self, root: TreeNode) -> list:
result = []
def helper(node):
if node is None:
return
helper(node.left)
result.append(node.value)
helper(node.right)
helper(root)
return result
# Brief example usage:
# t = TreeNode(5, TreeNode(3), TreeNode(7))
# sol = Solution()
# print(sol.inorderTraversal(t))
When constructing test cases, ensure you build proper TreeNode instances rather than passing plain lists or using identifiers like null. In Python, None serves as the sentinel for absent children. Also verify that the recursive function name matches its definition to avoid NameError.