inorder traversal Algorithm
Inorder traversal is a tree traversal algorithm, specifically designed for binary trees, where nodes are visited in a specific order: left subtree, root, and then right subtree. This algorithm is primarily used in binary search trees, where the nodes are sorted in such a way that elements in the left subtree are smaller than the root element, and the elements in the right subtree are larger than the root element. When traversing a binary search tree using inorder traversal, the resulting sequence of visited nodes will be in ascending order. Inorder traversal can be implemented using recursive or iterative approaches.
The recursive implementation of the inorder traversal algorithm starts at the root node and proceeds by recursively traversing the left subtree first, visiting the root node, and then recursively traversing the right subtree. The base case for the recursion occurs when an empty (null) subtree is encountered, at which point the recursive function returns without performing any action. The iterative approach, on the other hand, uses a stack data structure to track the nodes in the tree. The algorithm starts at the root node and pushes all the left children onto the stack until it reaches the leftmost node. Then, it pops a node from the stack, visits it, and moves to the right subtree, repeating the process of pushing left children onto the stack. This continues until the stack is empty and all the nodes have been visited.
# Definition for a binary tree node.
# class TreeNode
# attr_accessor :val, :left, :right
# def initialize(val)
# @val = val
# @left, @right = nil, nil
# end
# end
# @param {TreeNode} root
# @return {Integer[]}
def inorder_traversal(root)
ans = []
def traverse(node, ans)
if node != nil
traverse(node.left, ans)
ans.push(node.val)
traverse(node.right, ans)
end
end
traverse(root, ans)
return ans
end
