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
and1000000000
- 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)
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.