BinaryTreeInorderTraversal

Problem

https://leetcode.com/problems/binary-tree-inorder-traversal/

Solution

For an inorder traversal, visit the left subtree, then the root, then the right subtree recursively.

     root (2)
    /        \
left (1)  right (3)

Code

from typing import List


class TreeNode:
    """Node in a binary tree.
    """

    def __init__(self, val, left=None, right=None) -> None:
        self.val = val
        self.left = left
        self.right = right


def inorderTraversal(root: TreeNode | None) -> List[int]:
    """Traverse a binary tree in order from left to right.
    """
    if root is None:
        return []
    else:
        return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)

Test

>>> from BinaryTreeInorderTraversal import inorderTraversal, TreeNode
>>> root = TreeNode(1, None, TreeNode(2, TreeNode(3), None))
>>> inorderTraversal(root)
[1, 3, 2]
>>> root = None
>>> inorderTraversal(root)
[]
>>> root = TreeNode(1)
>>> inorderTraversal(root)
[1]

class BinaryTreeInorderTraversal.TreeNode(val, left=None, right=None)

Bases: object

Node in a binary tree.

BinaryTreeInorderTraversal.inorderTraversal(root: TreeNode | None) → List[int]

Traverse a binary tree in order from left to right.