// Created for this challenge: // https://www.ideserve.co.in/learn/diagonal-sum-of-a-binary-tree // Diagonal Sum of a Binary Tree. // Consider lines drawn at an angle of 135 degrees // (that is slope = -1) which cut through the left // branches of a given binary tree. A diagonal is // formed by nodes which lie between two such // consecutive lines. If we are able to draw 'n' // lines then the complete tree is divided into // 'n+1' diagonals. Diagonal sum in a binary tree // is sum of all node's values lying between these // lines. Given a binary tree, print all diagonal // sums. Please note that all right branches are // drawn parallel to each other and all left // branches are also drawn parallel to each other. // For example, // 0 // 1 2 // 4 5 3 6 // 7 // in the above tree there are total of three // diagonals. Diagonal-0 has 3 nodes in it: node-0, // node-2 and node-6. Therefore, sum of all nodes in // diagonal-0 is 8. Similarly, sum of nodes in // diagonal-1 is 9(node-1, node-5 and node-3). And // sum of nodes in diagonal-2 is 11(node-4, node-7). // Data class for the nodes of the binary tree. // Note: this is not meant to be processed in any // way beyond creating, printing, and summing. // The node contains a value plus optional left & // right nodes defaulting to null. data class Node(var value: Int, var left: Node? = null, var right: Node? = null) { // Overridden method to return a string of the // tree starting with this node. override fun toString(): String { // Create the resulting string and the default // lists for both left & right nodes. var result: String var first = List(0) { "" } var second = List(0) { "" } // If there is a left node, generate it's // string and split it on the new lines to // form the lists of levels. if (left != null) first = left.toString().split('\n') // If there is a right node, generate it's // string and split it on the new lines to // form the lists of levels. if (right != null) second = right.toString().split('\n') // If both nodes do not exist, the result is // this node's value. if (first.isEmpty() && second.isEmpty()) result = "$value" // Otherwise, we had some nodes below this one // so put them together. else { // Figure out how many levels below this node // exist, create an array with elements for // those levels plus this one, and for each // of those lower levels, merge their strings. val size = Math.max(first.size, second.size) val array = Array(size+1) { "" } for (index in size-1 downTo 0) // If both sides have this level, combine // them. if (index < first.size && index < second.size) { when { // When the left side string is shorter // than the right side, we pad both // sides of it with a space until it // is the same length (reusing the // result) followed by combining both // strings into our array. first[index].length < second[index].length -> { result = " ${first[index]} " while (result.length < second[index].length) result = " $result " array[index+1] = "$result ${second[index]}" } // first // When the right side string is shorter // than the left side, we pad both // sides of it with a space until it // is the same length (reusing the // result) followed by combining both // strings into our array. first[index].length > second[index].length -> { result = " ${second[index]} " while (result.length < first[index].length) result = " $result " array[index+1] = "${first[index]} $result" } // second // When both strings are the same // length, we can just combine them // both into our array. else -> array[index+1] = "${first[index]} ${second[index]}" } // when // Otherwise, if there is only a left // side node at this level, this level // gets the left string with enough spaces // to fill in the right side. } else if (index < first.size) array[index+1] = first[index]+" ".repeat( first[index].length+1) // Otherwise, there is only a right side // node at this level, this level gets // enough spaces to fill in the left side // with the right string. else array[index+1] = " ".repeat( second[index].length+1)+second[index] // Put this node's value in the new level. // Adjust the string's length by adding a // space before and after it's current value // until it matches the length of the lower // level. Convert our array into the result // string by putting a new line between each // level's string. array[0] = " $value " while (array[0].length < array[1].length) array[0] = " ${array[0]} " result = array.joinToString("\n") } // if return result } // toString } // Node // Class for the binary tree. Note: this is not // meant to be processed in any way beyond creating, // printing, and summing. class Tree(private val root: Node? = null) { // Method to traverse the tree to generate the // list of sums. Default the sums to an empty // list. fun sum(): List { val list = mutableListOf() // Recursive function to process a node. fun process(node: Node?, level: Int) { // If there is a node, process it. if (node != null) { // If we are missing a list element for // this level, add it as zero. if (level == list.size) list.add(0) // Add the current value to the current // level's sum. Process the left node at // the next higher level. The right node // is processed at the same level as this // node. list[level] += node.value process(node.left, level+1) process(node.right, level) } // if } // process // Start the tree traversal. process(root, 0) return list.toList() } // sum // Overridden method to return a string of the // tree starting with the root. override fun toString() = root.toString() } // Tree // Main function to prove the code with a few test // cases. For each test, display the tree and the // sums. fun main(args: Array) { for (tree in listOf( Tree(Node(0, Node(1, Node(4), Node(5, Node(7))), Node(2, Node(3), Node(6)))), Tree(Node(5, Node(1, Node(3), Node(7, Node(8))), Node(2, Node(4, Node(0, Node(9))), Node(6)))), Tree(Node(2, Node(4, Node(5)))), Tree())) { println(tree) println("Sums: ${tree.sum()}") } // for } // main

treeSum ch