In-order Traversal of Binary Search Tree

In-order Traversal of Binary Search Tree

The In-order Traversal of a Binary Search Tree (BST) visits the nodes in a specific order: left subtree, root, then right subtree. For a BST, this results in visiting the nodes in ascending order of their values, making it a useful operation for retrieving sorted elements. The algorithm can be implemented recursively or iteratively, with the recursive approach being simpler to understand. The time complexity is O(n), where n is the number of nodes, and the space complexity is O(h) for recursion, where h is the height of the tree.

Example:

• Input: BST with nodes [5, 3, 7, 1, 4]
• Output: [1, 3, 4, 5, 7]
• Explanation: The in-order traversal visits nodes in ascending order.

Logic

Enter a list of numbers (comma-separated) to create a Binary Search Tree and perform an in-order traversal to get the sorted list.

Program (Python - In-order Traversal of BST)

The following Python code implements a recursive in-order traversal of a BST with O(n) time complexity and O(h) space complexity, where n is the number of nodes and h is the tree height. It also includes helper functions to build the BST.

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

def insertNode(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insertNode(root.left, val)
    else:
        root.right = insertNode(root.right, val)
    return root

def inorderTraversal(root):
    result = []
    if root:
        # Traverse left subtree
        result.extend(inorderTraversal(root.left))
        # Visit root
        result.append(root.val)
        # Traverse right subtree
        result.extend(inorderTraversal(root.right))
    return result

# Helper function to create BST from array
def createBST(arr):
    root = None
    for val in arr:
        root = insertNode(root, val)
    return root

# Example usage
arr = [5, 3, 7, 1, 4]
root = createBST(arr)
print(inorderTraversal(root))  # Output: [1, 3, 4, 5, 7]

[1, 3, 4, 5, 7]