Good morning! 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

  console.log('PASSED: ' + '`stringFromTree(tree1)` should return `4[[1][3]]`');

var assert = require('assert');

​

function stringFromTree(tree) {

  // fill in

  return tree;

}

​

class Node {

  constructor(value) {

    this.val = value;

    this.left = null;

    this.right = null;

  }

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

Here's our guided, illustrated walk-through.

How do I use this guide?