Rosetta Code

Tree traversal

Traverse a small binary tree in preorder, inorder, postorder, and level order.

Edit the source, then Run. Checks start after your first Run. Ctrl/⌘ + Enter runs; Tab indents. Preview services use sample data and never contact a real service.

Sourcerosettacode/popular/tree_traversal.vibe
type RunResult = {
  preorder: array<string>,
  inorder: array<string>,
  postorder: array<string>,
  level_order: array<string>
}

class Node
  getter value: string
  getter left: Node?
  getter right: Node?

  def initialize(@value: string, @left: Node? = nil, @right: Node? = nil)
  end
end

def sample_tree -> Node
  Node.new("F",
    Node.new("B", Node.new("A"), Node.new("D", Node.new("C"), Node.new("E"))),
    Node.new("G", nil, Node.new("I", Node.new("H"))))
end

def preorder(node: Node?) -> array<string>
  return [] if node == nil
  [node.value] + preorder(node.left) + preorder(node.right)
end

def inorder(node: Node?) -> array<string>
  return [] if node == nil
  inorder(node.left) + [node.value] + inorder(node.right)
end

def postorder(node: Node?) -> array<string>
  return [] if node == nil
  postorder(node.left) + postorder(node.right) + [node.value]
end

def level_order(root: Node?) -> array<string>
  return [] if root == nil
  queue = [root]
  output: array<string> = []
  index = 0
  while index < queue.length
    current = queue.fetch(index)
    output << current.value
    left = current.left
    right = current.right
    queue << left if left != nil
    queue << right if right != nil
    index += 1
  end
  output
end

def run -> RunResult
  tree = sample_tree
  {
    preorder: preorder(tree),
    inorder: inorder(tree),
    postorder: postorder(tree),
    level_order: level_order(tree)
  }
end

Output

Click Run example to see the result.

Code checks

Run once to load the checker. Your code stays in this browser.