Tree Manager – HackerRank Solution

In this post, we will solve Tree Manager HackerRank Solution. This problem (Tree Manager) is a part of HackerRank Functional Programming series.

Task

In this problem you must perform operations on a rooted tree storing integers in each node. There are several operations to handle:

• changeValue(x)– Changes the value stored in the current node to x.
• print() – Prints the values stored in the current node.
• visitLeft() – Sets the current node to be the left sibling of the current node.
• visitRight() – Sets the current node to be the right sibling of the current node.
• visitParent() – Sets the current node to be the parent of the current node.
• visitChild(n) – Sets the current node to be the n^th child of the current node. Children are numbered from left to right starting from 1.
• insertLeft(x) – Inserts a new node with value x as the left sibling of the current node.
• insertRight(x) – Inserts a new node with value x as the right sibling of the current node.
• insertChild(x) – Inserts a new node as the leftmost child of the current node.
• delete() – Deletes the current node with the subtree rooted in it and sets the current node as a parent of just deleted node.

Knowing that the tree initially consists of the root with value 0, your task is to perform Q consecutive operations.

Check the Input Format section for a description of how each operation is given in the input, and review the Constraints section to clarify which operations are not allowed for the root node.

Input Format

The first line contains a single integer, Q, denoting the number of operations to perform. The Q subsequent lines each describe a single operation to perform. The operations are coded as follows:

• change x -> changeValue(x)
• print -> print()
• visit left -> visitLeft()
• visit right -> visitRight()
• visit parent -> visitParent()
• visit child n -> visitChild(n)
• insert left x -> insertLeft(x)
• insert right x -> insertRight(x)
• insert child x -> insertChild(x)
• delete -> delete()

Constraints

• 1 <= Q <= 10⁵
• 0 <= x <= 10⁶
• 1 <= n <= 10
• It is guaranteed that all operations given as input will be valid.

Invalid operations are:

• Visiting left/right sibling when there is no such sibling.
• Visiting the n^th child when there are less than n children.
• Deleting the root.
• Inserting any sibling of the root.
• A single node will never have more than 10 children.

Output Format

For each print() operation, output a single line with the value in the current node.

Sample Input

11
change 1
print
insert child 2
visit child 1
insert right 3
visit right
print
insert right 4
delete
visit child 2
print

Sample Output

1
3
4

Explanation

There are 11 operations to handle.
At the beginning, we change the value stored in the root to 1 and then we print it.
After that, we insert a new child of the root with value 2.
Then, we visit this child and insert a new node with value 3 as its right sibling.
Next, we visit the last inserted node and print its value.
After that, we insert a new node with value 4 as the right sibling of last inserted node.
Then, we delete the current node (the one with value 3), so the current node becomes the root.
Next, we visit the second child of the root, which is the last inserted node with value 4 (because we deleted the node with value 3).
Finally, we print the value stored in the current node, which is 4.

Solution – Tree Manager – HackerRank Solution

Scala

import java.util.Scanner

trait Tree {
  def value: Int

  def value_=(v: Int): Unit

  def children: Array[Tree]

  def children_=(v: Array[Tree]): Unit

  def parent: Tree
}

object Tree {
  val MaxChildCount = 10

  def createChildren: Array[Tree] = Array.ofDim[Tree](Tree.MaxChildCount)
}

class Node(var value: Int, val parent: Tree, var children: Array[Tree]) extends Tree

case object Empty extends Tree {
  override def value: Int = exception

  override def value_=(v: Int): Unit = exception

  override def children: Array[Tree] = exception

  override def children_=(v: Array[Tree]): Unit = exception

  private def exception = throw new Exception("The operation is not supported.")

  override def parent: Tree = exception
}

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val q = sc.nextInt
    sc.nextLine

    val root = new Node(0, Empty, Tree.createChildren)
    var current: Tree = root

    (0 until q).foreach(_ => {
      val tokens = sc.nextLine.split(" ")

      tokens.head match {
        case "change" => current.value = tokens(1).toInt
        case "print" => println(current.value)
        case "visit" => tokens(1) match {
          case "left" =>
            val index = current.parent.children.indexOf(current)
            current = current.parent.children(index - 1)
          case "right" =>
            val index = current.parent.children.indexOf(current)
            current = current.parent.children(index + 1)
          case "parent" =>
            current = current.parent
          case "child" =>
            current = current.children(tokens(2).toInt - 1)
        }
        case "insert" =>
          def insertSibling(pos: Int): Unit = {
            val node = new Node(tokens(2).toInt, current.parent, Tree.createChildren)
            val index = current.parent.children.indexOf(current) + pos
            current.parent.children = (current.parent.children.take(index) :+ node) ++ current.parent.children.drop(index)
          }

          tokens(1) match {
            case "left" =>
              insertSibling(0)
            case "right" =>
              insertSibling(1)
            case "child" =>
              val node = new Node(tokens(2).toInt, current, Tree.createChildren)
              current.children = node +: current.children
          }
        case "delete" =>
          val temp = current
          current = current.parent
          current.children = current.children.filter(_ != temp) :+ Empty
      }
    })

    sc.close()
  }
}

Note: This problem (Tree Manager) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.