August 27, 2024
P56 - Symmetric binary trees.
Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Add an isSymmetric method to the Tree to check whether a given binary tree is symmetric.
Hint: Write isMirrorOf method first to check whether one tree is the mirror image of another. We are only interested in the structure, not in the contents of the nodes.
> Node("a", Node("b"), Node("c")).isSymmetric()
truekotlin
package org.kotlin99.binarytrees
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
import org.kotlin99.binarytrees.Tree.End
import org.kotlin99.binarytrees.Tree.Node
fun Tree<*>.isSymmetric(): Boolean = this == End || (this is Node<*> && left.isMirrorOf(right))
fun Tree<*>.isMirrorOf(that: Tree<*>): Boolean =
when {
this is Node<*> && that is Node<*> -> left.isMirrorOf(that.right) && right.isMirrorOf(that.left)
this == End -> that == End
else -> false
}
class P56Test {
@Test fun `tree is mirror of another tree`() {
assertThat(Node("x").isMirrorOf(Node("x")), equalTo(true))
assertThat(Node("x").isMirrorOf(Node("x", Node("x"))), equalTo(false))
assertThat(Node("x", End, Node("x")).isMirrorOf(Node("x", End, Node("x"))), equalTo(false))
assertThat(Node("x", End, Node("x")).isMirrorOf(Node("x", Node("x"))), equalTo(true))
}
@Test fun `tree is symmetric`() {
assertThat(Node("x").isSymmetric(), equalTo(true))
assertThat(Node("x", Node("x")).isSymmetric(), equalTo(false))
assertThat(Node("x", End, Node("x")).isSymmetric(), equalTo(false))
assertThat(Node("x", Node("x"), Node("x")).isSymmetric(), equalTo(true))
assertThat(Node("x", Node("x", End, Node("x")), Node("x", Node("x"))).isSymmetric(), equalTo(true))
}
}
Be first to comment