Scala algorithm: Check a binary tree is balanced
A binary tree is considered to be balanced when the height of each sub-branch of a tree has a height that differs by no more than 1, and its children also are balanced.
Test cases in Scala
Algorithm in Scala
31 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!
To check if a tree is balanced, we need to check the height and also that both of the sub-trees are balanced.
Here we demonstrate two approaches to iterating a tree: 'isBalanced' uses a recursive approach where it would call both 'left.isBalanced' and 'right.isBalanced', which would create a stack of size of the height of the tree, so is not the most efficient stack-wise; for 'heightIterative', we use an iterative approach which uses more heap but less stack (no recursion). . (this is © from www.scala-algorithms.com)
Scala concepts & Hints
'collect' allows you to use Pattern Matching, to filter and map items.
Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.
A state machine is the use of `sealed trait` to represent all the possible states (and transitions) of a 'machine' in a hierarchical form.