How to stdout Hackerrank Binary Tree question in TypeScript?

user_15008709 0
Viewed 228

Here is the Hackerrank question:

Given a pointer to the root of a binary tree, you need to print the level order traversal of this tree. In level-order traversal, nodes are visited level by level from left to right. Complete the function and print the values in a single line separated by a space.

I already defined the function levelOrder(). However don't know how to stdout. Also why is no Node class is given here. When I checked other languages like Java for this question, I saw that Node class was declared. How can they expect me to take strings as, act as they are nodes. I am confused.

Here is entire code in the hackerrank editor including their setup:

'use strict';

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString: string = '';
let inputLines: string[] = [];
let currentLine: number = 0;
process.stdin.on('data', function(inputStdin: string): void {
    inputString += inputStdin;
});

process.stdin.on('end', function(): void {
    inputLines = inputString.split('\n');
    inputString = '';
    main();
});

function readLine(): string {
    return inputLines[currentLine++];
}

function main() {
    // Enter your code here
    
    function levelOrder(root: any): string {
        const queue = [root];
        let visited = "";
        let currentNode = root;
        while (queue.length > 0) {
            currentNode = queue.shift();
            visited += `${currentNode.val} `;
            if (currentNode.left) queue.push(currentNode.left);
            if (currentNode.right) queue.push(currentNode.right);
        }
        return visited;
    }
    // How I am going to invoke my function and stdout return val here?
}
typescript node.js binary-tree
1 Answers

You are right that this is confusing.

Apparently, HackerRank has not really put much effort in the TypeScript versions of the code challenges, as there is no provision in the template code for converting the text input into a TreeNode data structure, like is done for the other languages.

Secondly, the challenge does not explain either how the text based input is organised. For this, I looked at some other binary tree challenges on HackerRank, and found that for this one that input format is described:

The first line contains an integer , the number of nodes in the tree. Next line contains space separated integer where th integer denotes node[i].data.

Note: Node values are inserted into a binary search tree before a reference to the tree's root node is passed to your function. In a binary search tree, all nodes on the left branch of a node are less than the node value. All values on the right branch are greater than the node value.

So, the binary tree is actually a binary search tree! And the input values should be inserted into it in that order to finally construct the tree that is the subject of the challenge.

For some mysterious reason you must do this yourself when solving the challenge in TypeScript and not in other languages.

For what concerns output, you can just use console.log.

Here is some generic code you could use for solving binary tree questions on HackerRank with TypeScript:

class TreeNode {
    left: TreeNode;
    right: TreeNode;
    data: number;
    
    constructor(value: number) {
        this.data = value;
        this.left = null;
        this.right = null;
    }
}

function insertNode(node: TreeNode, data: number): TreeNode {
    if (node === null) return new TreeNode(data);
    if (data < node.data) {
        node.left = insertNode(node.left, data);
    } else {
        node.right = insertNode(node.right, data);
    }
    return node;
}

function inputTree(): TreeNode {
    const nodeValues = inputLines[1].match(/\d+/g).map(Number);
    let root: TreeNode = null;
    for (const nodeValue of nodeValues) {
        root = insertNode(root, nodeValue);
    }
    return root;
}

With that in place, your main code could have this structure:

function main() {
    const root = inputTree();
    const result = /* your solution code here, producing an array */;
    console.log(result.join(" "));
}

To complete my answer, I provide here a spoiler for how I would have written the core of the solution for this particular code challenge, but I guess with the above you really have enough:

function* levelOrder(root: TreeNode) { const queue: TreeNode[] = [root]; for (let i = 0; i < queue.length; i++) { const node = queue[i]; yield node.data; if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } } function main() { const root = inputTree(); const result = [...levelOrder(root)]; console.log(result.join(" ")); }

user_54598390
Related