Good afternoon! Here's our prompt for today.

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

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

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

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?

xxxxxxxxxx

​

def stringFromTree(tree):

    # fill in

    return ""

​

​

# Node definition

class Node:

    def __init__(self, val):

        self.val = val

        self.left = None

        self.right = None

​

​

# Regular binary trees

tree1 = Node(4)

tree1.left = Node(1)

tree1.right = Node(3)

​

tree2 = Node(5)

tree2.left = Node(10)

tree2.left.left = Node(17)

tree2.left.right = Node(3)

tree2.right = Node(8)

​

# Binary search trees

tree3 = Node(6)

tree3.left = Node(3)

​

tree4 = Node(5)

Here's our guided, illustrated walk-through.

How do I use this guide?