DFS on Binary Tree

EasyPython00:00

Practice interviewer

In session

5 left

00:00

Your question is DFS on Binary Tree. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

You need to log in / sign up to run or submit.

Problem

PingOne authorization policies can be represented as binary decision trees. Given the root of a binary tree, implement dfs_preorder(root) to visit every node using depth-first search and return the node values in preorder: visit the current node, then its left subtree, then its right subtree.

Represent each node as a dictionary with keys value, left, and right. A missing child is represented by None.

Formal Specification

Input: root, either None or a nested binary-tree dictionary. Each value is an integer.
Output: A list of integers containing the values visited in preorder.
The function must visit every reachable node exactly once.

Constraints

0 <= number of nodes <= 10^5
Node values are integers in the range [-10^9, 10^9]
The input is a valid binary tree
Each node has at most one left child and one right child

Function Signature

def dfs_preorder(root):

Your solutionPython 3

You need to log in / sign up to run or submit.

Run your code to see test output