Binary Tree Preorder Traversal
Binary Tree Preorder Traversal is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
Problem statement
A binary tree is a structure in which each node has a value and up to two children: a left child and a right child. root refers to the top node of the tree; a missing child is represented by null in the level-order input, and an empty tree is represented by [].
Traverse the tree in preorder: visit the current node first, then traverse its entire left subtree, and finally traverse its entire right subtree. Return a list containing the visited node values in that order.
Do not modify the tree. If root is empty, return an empty list.
Example 1:
Input: root = [8,3,null,1,6,null,null,4,7] Output: [8,3,1,6,4,7] Explanation: The root is visited before its descendants; within the left subtree, 3 comes before 1 and 6, and 6 comes before its children 4 and 7.
Example 2:
Input: root = [5] Output: [5] Explanation: A tree with one node has that node as its entire preorder traversal.
Example 3:
Input: root = [10,null,12,null,14] Output: [10,12,14] Explanation: Each node has only a right child, so preorder visits the nodes from the root down that right-hand chain.
Constraints:
- 0 <= number of nodes in root <= 100 - -100 <= each node value <= 100 - Each node has at most one left child and at most one right child - root is a valid binary tree encoded in level order, using null for missing children
Topics and companies
Topics: Binary Tree, Tree, Depth-First Search, Recursion.
How to practise Binary Tree Preorder Traversal on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the number of nodes in the tree. time and O(h) auxiliary space for the recursion stack, where h is the tree height; O(n) including the returned result. space.
Open Binary Tree Preorder Traversal in the code editor, or read the Binary Tree Preorder Traversal editorial for a worked solution with its approach and complexity analysis.
Where Binary Tree Preorder Traversal sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Preorder Traversal subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Binary Tree Preorder Traversal
Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Paths — Easy, same subpattern
- Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
- Construct Quad Tree — Medium, same subpattern
- Count Good Nodes in Binary Tree — Medium, same subpattern
- Flatten Binary Tree to Linked List — Medium, same subpattern
- Insert into a Binary Search Tree — Medium, same subpattern