Inorder Tree Traversal

Example: Let's consider an example to understand Inorder Tree Traversal better. We'll create a binary tree and perform the inorder traversal on it.

# Node class definition
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Function to perform inorder traversal
def inorderTraversal(root):
    result = []
    stack = []

    # Start with the root node
    current = root

    while current or stack:
        # Traverse to the leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Visit the top node from the stack
        current = stack.pop()
        result.append(current.val)

        # Move to the right subtree
        current = current.right

    return result

# Create a binary tree
root = TreeNode(1)
root.right = TreeNode(2)
root.right.left = TreeNode(3)

# Perform inorder traversal
inorder = inorderTraversal(root)
print("Inorder Traversal:", inorder)
# Output: Inorder Traversal: [1, 3, 2] 

In this example, we define a function inorderTraversal that takes the root of a binary tree as input and returns the inorder traversal of the tree as a list.

We use an iterative approach to perform the inorder traversal. We maintain a stack to keep track of the nodes. We start with the root node and traverse to the leftmost node, pushing each node onto the stack. Once we reach the leftmost node, we pop the top node from the stack, visit it, and then move to its right subtree. We repeat this process until there are no more nodes to visit.

In the main code, we create a binary tree with the following structure:

    1
     \
      2
     /
    3

We then call the inorderTraversal function with the root of the binary tree. The function performs the inorder traversal and returns the result.

In this case, the inorder traversal of the binary tree is [1, 3, 2].

The time complexity of the inorder traversal is O(n), where n is the number of nodes in the binary tree, as we need to visit each node exactly once. The space complexity is O(h), where h is the height of the binary tree, as the maximum number of nodes stored in the stack at any point is equal to the height of the tree.

Let's solve a question that involves the concept of Inorder Tree Traversal. The problem we'll solve is "Validate Binary Search Tree".

Problem Statement: Given the root of a binary tree, determine if it is a valid binary search tree (BST).

Example:

# Node class definition
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Function to perform inorder traversal
def inorderTraversal(root):
    result = []
    stack = []

    # Start with the root node
    current = root

    while current or stack:
        # Traverse to the leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Visit the top node from the stack
        current = stack.pop()
        result.append(current.val)

        # Move to the right subtree
        current = current.right

    return result

# Function to check if a binary tree is a valid BST
def isValidBST(root):
    # Perform inorder traversal
    inorder = inorderTraversal(root)

    # Check if the inorder list is sorted
    for i in range(1, len(inorder)):
        if inorder[i] <= inorder[i - 1]:
            return False

    return True

# Create a binary tree
root = TreeNode(2)
root.left = TreeNode(1)
root.right = TreeNode(3)

# Check if the binary tree is a valid BST
is_valid = isValidBST(root)
print("Is Valid BST?", is_valid)
# Output: Is Valid BST? True 

In this example, we define two functions: inorderTraversal and isValidBST.

The inorderTraversal function performs the inorder traversal of a binary tree and returns the traversal result as a list. We use an iterative approach with a stack to simulate the traversal process. This function is the same as explained in the previous example.

The isValidBST function checks if a binary tree is a valid BST. It calls the inorderTraversal function to get the inorder traversal of the tree. Then, it checks if the obtained list is sorted in ascending order. If any element is smaller or equal to its previous element in the list, it returns False, indicating that the tree is not a valid BST. Otherwise, it returns True.

In the main code, we create a binary tree with the following structure:

    2
   / \
  1   3

We then call the isValidBST function with the root of the binary tree. The function performs the inorder traversal using the inorderTraversal function and checks if the obtained list [1, 2, 3] is sorted. Since it is sorted in ascending order, the binary tree is considered a valid BST.

The time complexity of this approach is O(n), where n is the number of nodes in the binary tree, as we perform an inorder traversal of the tree. The space complexity is O(h), where h is the height of the binary tree, as we use a stack to store nodes during traversal.