Created
August 10, 2019 14:10
-
-
Save serragnoli/dedaae2dc03e6b99b9dbe844901ac996 to your computer and use it in GitHub Desktop.
Tree - add() and search()
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| case class TreeNode(left: Option[TreeNode], value: Int, right: Option[TreeNode]) | |
| object TreeNode { | |
| def empty: TreeNode = TreeNode(None, 0, None) | |
| } | |
| case class Tree(rootNode: TreeNode) { | |
| def add(valToAdd: Int): Tree = { | |
| def addRec(recValToAdd: Int, recCurrNode: TreeNode): TreeNode = { | |
| recCurrNode match { | |
| case TreeNode(None, 0, None) => TreeNode(None, recValToAdd, None) | |
| case node@TreeNode(_, nodeVal, _) if nodeVal == recValToAdd => node | |
| case node@TreeNode(None, nodeVal, None) => | |
| if (nodeVal <= recValToAdd) node.copy(right = Option(TreeNode(None, recValToAdd, None))) | |
| else node.copy(left = Option(TreeNode(None, recValToAdd, None))) | |
| case node@TreeNode(Some(ln), nodeVal, None) => | |
| if (nodeVal <= recValToAdd) node.copy(right = Option(addRec(recValToAdd, ln))) | |
| else node.copy(left = Option(TreeNode(None, recValToAdd, None))) | |
| case node@TreeNode(None, nodeVal, Some(rn)) => | |
| if (nodeVal <= recValToAdd) node.copy(right = Option(addRec(recValToAdd, rn))) | |
| else node.copy(left = Option(TreeNode(None, valToAdd, None))) | |
| case node@TreeNode(Some(ln), nodeVal, Some(rn)) => | |
| if (nodeVal <= recValToAdd) node.copy(right = Option(addRec(recValToAdd, rn))) | |
| else node.copy(left = Option(addRec(recValToAdd, ln))) | |
| } | |
| } | |
| val updatedTreeNodes = addRec(valToAdd, rootNode) | |
| Tree(updatedTreeNodes) | |
| } | |
| def search(wantedVal: Int): Option[Int] = { | |
| @tailrec | |
| def recSearch(recWantedVal: Int, recNode: TreeNode): Option[Int] = { | |
| recNode match { | |
| case TreeNode(_, n, _) if n == recWantedVal => Option(recWantedVal) | |
| case TreeNode(None, _, None) => None | |
| case TreeNode(Some(ln), nodeVal, None) => | |
| if (nodeVal <= recWantedVal) None | |
| else recSearch(recWantedVal, ln) | |
| case TreeNode(None, nodeVal, Some(rn)) => | |
| if (nodeVal <= recWantedVal) recSearch(recWantedVal, rn) | |
| else None | |
| case TreeNode(Some(ln), nodeVal, Some(rn)) => | |
| if (nodeVal <= recWantedVal) recSearch(recWantedVal, rn) | |
| else recSearch(recWantedVal, ln) | |
| } | |
| } | |
| recSearch(wantedVal, rootNode) | |
| } | |
| } | |
| object Tree { | |
| def empty = Tree(TreeNode.empty) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment