Preorder traversal

The node first, then its left subtree, then its right subtree. Parents always come before their children.

Time O(n)Space O(h)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Record the node the moment you arrive, then handle the children. The result starts with the root and lists every parent before anything beneath it.

Code

C++PythonC#

void preorder(TreeNode* node, vector<int>& result) {
    if (!node) return;
    result.push_back(node->val);
    preorder(node->left, result);
    preorder(node->right, result);
}

def preorder(node: TreeNode | None, result: list[int]) -> None:
    if node is None: return
    result.append(node.val)
    preorder(node.left, result)
    preorder(node.right, result)

public static void Preorder(TreeNode node, List<int> result) {
    if (node == null) return;
    result.Add(node.val);
    Preorder(node.left, result);
    Preorder(node.right, result);
}

Tips

Use it to copy or serialise a tree: inserting the keys in preorder rebuilds the same BST.

In the .NET library

A recursive file listing that prints each directory before its contents, like Directory.EnumerateDirectories with your own recursion, is a preorder walk.