FastPrep
Problem · Tree

Binary Tree Preorder Traversal

Learn this problem
● EasyAnduril logoAndurilFULLTIMEONSITE INTERVIEW

Problem statement

You are given a binary tree serialized in a heap-indexed integer array tree. For a node at index i, its left child is at 2 * i + 1 and its right child is at 2 * i + 2. The value -1 marks a missing node.

Return the values of the existing nodes in preorder: visit the root, then the left subtree, then the right subtree.

An empty array or an array whose root is -1 represents an empty tree and returns an empty array.

Function

preorderTraversal(tree: int[]) → int[]

Examples

Example 1

tree = [1,2,3,-1,4,5,6]return = [1,2,4,3,5,6]

Visit 1, then its left subtree 2, 4, followed by its right subtree 3, 5, 6.

Example 2

tree = [7,-1,9,-1,-1,8,10]return = [7,9,8,10]

The left child of 7 is missing, so preorder continues through the right subtree rooted at 9.

Constraints

  • 0 <= tree.length <= 10^5.
  • Each array entry is either -1 or an integer in the range [0, 10^9].
  • Every nonmissing node other than the root has a nonmissing parent.
  • Indexes beyond tree.length - 1 represent missing nodes.

More Anduril problems

drafts saved locally
public int[] preorderTraversal(int[] tree) {
    // write your code here
}
tree[1,2,3,-1,4,5,6]
expected[1,2,4,3,5,6]
checking account