Mark As Completed Discussion

Good afternoon! Here's our prompt for today.

Suppose we're given a simple binary tree like the following:

JAVASCRIPT
1      1
2     / \
3    2   3
4         \
5          4     

Can you generate a string based off the values of its nodes?

Description

With this string, we're going to want to capture the number/key at each node, as well as model the relationships between nodes. The order the nodes appear in the string would be based on the tree's pre-order traversal.

Let's look at an example of this peculiar format. In the tree above, we have nodes 1, 2, 3, and 4. We'll use brackets to represent the child nodes of a node.

Note that in our tree, 2 and 3 are children of 1. The relationship can be represented like:

1[[2][3]]

To expand on the string, the child of 3 would be added in this manner:

1[[2][3[[4]]]]

Note the use of double brackets. Each child node aside from the root should be wrapped in its own set of brackets.

Where there are no nodes present (e.g. 3 has no left child node), we can simply skip that iteration. The method will be called via stringFromTree(tree).

Constraints

  • The number of nodes in the binary tree would be <= 100000
  • The nodes will always contain integer values between -1000000000 and 1000000000
  • Expected time complexity : O(n)
  • Expected space complexity : O(logn)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

PYTHON
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

We'll now take you through what you need to know.

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.