Binary Tree Paths

Binary Tree Paths 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

Given the root of a binary tree, return all root-to-leaf paths in any order.

A leaf is a node with no children.

Example 1:

Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"]

Example 2:

Input: root = [1] Output: ["1"]

Constraints:

- The number of nodes in the tree is in the range [1, 100].

- -100 <= Node.val <= 100

Topics and companies

Topics: String, Backtracking, Tree, Depth-First Search, Binary Tree.

Reported in interviews at Facebook, Google, Apple, Bloomberg.

How to practise Binary Tree Paths on Thita.ai

Starter code is provided in C, 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 * h) time and O(h) space.

Open Binary Tree Paths in the code editor, or read the Binary Tree Paths editorial for a worked solution with its approach and complexity analysis.

Where Binary Tree Paths 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 Paths

Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:

• Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
• Flatten Binary Tree to Linked List — Medium, same subpattern
• Invert Binary Tree — Easy, same subpattern
• Same Tree — Easy, same subpattern
• Smallest String Starting From Leaf — Medium, same subpattern
• Symmetric Tree — Easy, same subpattern