Binary Tree Implementation in Scala

1. Introduction

A Binary Tree is a data structure composed of nodes. Each node contains a value, and it can have up to two child nodes, commonly referred to as the left and right child. A Binary Tree is a foundational concept in computer science and is a precursor to more specialized trees like binary search trees, AVL trees, and more.

2. Implementation Steps

1. Define the Node class, which will represent each element of the tree, containing the data, a left child, and a right child.

2. Implement the BinaryTree class with methods to:

- Insert elements into the tree (insert).

- Traverse and display the tree using In-Order traversal (inOrder).

3. Write the client code to test the Binary Tree implementation.

3. Implementation in Scala

// Definition for a Node in Binary Tree
class Node[A](var data: A, var left: Node[A] = null, var right: Node[A] = null)

class BinaryTree[A] {
  var root: Node[A] = null
  
  // Insert a new node with the given data into the tree
  def insert(data: A): Unit = {
    root = insertRec(root, data)
  }
  
  private def insertRec(node: Node[A], data: A): Node[A] = {
    if (node == null) {
      return new Node(data)
    }
    if (data.hashCode() < node.data.hashCode()) {
      node.left = insertRec(node.left, data)
    } else if (data.hashCode() > node.data.hashCode()) {
      node.right = insertRec(node.right, data)
    }
    node
  }
  
  // In-Order Traversal (Left, Root, Right)
  def inOrder(): Unit = {
    inOrderRec(root)
  }
  
  private def inOrderRec(node: Node[A]): Unit = {
    if (node != null) {
      inOrderRec(node.left)
      print(node.data + " ")
      inOrderRec(node.right)
    }
  }
}

Client Code:

val tree = new BinaryTree[Int]
tree.insert(50)
tree.insert(30)
tree.insert(70)
tree.insert(20)
tree.insert(40)
tree.insert(60)
tree.insert(80)
tree.inOrder()      // Expected Output: 20 30 40 50 60 70 80

Output:

20 30 40 50 60 70 80

Explanation:

1. class Node[A](var data: A, var left: Node[A] = null, var right: Node[A] = null): This represents our generic Node with data, a left child, and a right child.

2. class BinaryTree[A]: This initializes our BinaryTree class.

3. insert(data: A): Public method to insert data into the tree.

4. insertRec(node: Node[A], data: A): A recursive helper method to find the correct spot and insert the data. It uses the hashCode() to determine where to place the data, ensuring that values are placed to the left if they are smaller and to the right if they are larger.

5. inOrder(): Public method for In-Order Traversal of the tree.

6. inOrderRec(node: Node[A]): Recursive helper function for In-Order Traversal. It visits the left subtree, the root node, and then the right subtree in that order.

This provides a fundamental structure and basic operations of a Binary Tree in Scala.