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.


Related Scala Source Code Examples:

Scala program to print hello world Scala program to find the factorial of a number Scala program to check if a number is prime Scala program to find the Fibonacci series Scala program to reverse a string Scala program to count vowels in a string Scala program to implement bubble sort Scala program to find the largest element in an array Scala program to perform matrix multiplication Scala program to add two number Scala program to find prime numbers Scala program to check palindrome Scala program to find the maximum and minimum of an array Scala program to calculate the area of a circle Scala program to find the GCD of two numbers Scala program to check if a string is a palindrome Scala program to find the sum of digits of a number Scala program to count the number of words in a sentence Scala program to remove duplicates from a list Scala program to find the power of a number using recursion Scala program to convert Celsius to Fahrenheit Scala program to calculate compound interest Scala program to find the common elements in two arrays Scala program to check if two strings are anagrams Scala program to replace all occurrences of a substring Scala program to find the longest substring without repeating characters Scala program to split a string by a delimiter Scala program to find the sum and average of elements in an array Scala program to reverse an array Scala program to check if an array contains a specific value Scala program to merge two arrays Scala program to remove duplicates from an array Scala program to find the intersection of two arrays Scala program to find the rotation point in a rotated sorted array Scala program to find the power of a number Scala program to find all divisors of a number Scala program to reverse a list Scala program to concatenate two lists Scala program to find the last element in a list Scala program to remove duplicates from a list Scala program to sort a list of numbers Scala program to find the intersection of two lists Scala program to implement tail recursion Scala program to use Option, Some, and None for null safety Scala - custom flatMap or map function Scala program to calculate leap years Scala - Data Types Example Scala - Access Modifiers Example Scala - Arithmetic Operators Example Scala - Relational Operators Example Scala - Logical Operators Example Scala - Bitwise Operators Example Scala - IF ELSE Statements Example Scala - Loop Statements Example Scala - Functions Example Scala - Closures Example Scala - String Functions with Examples Scala - Array Functions with Examples Scala List Methods with Examples Scala Set Methods with Examples Scala Map Methods with Examples Scala - Tuples Example Scala - Exception Handling Example Scala Iterate Over an Array Scala Iterate Over List (Different Ways) Scala Iterate Over Map (Different Ways) Scala Iterate List With Index Scala Iterate Over List of Objects (Different Ways) Scala Iterate Over String Scala Convert List to Map Scala Convert String to Int Scala Convert String to Boolean Scala Convert String to Timestamp Scala Convert String to JSON Scala Convert String to Long Scala Convert Date to Epoch Scala Convert Map to JSON Scala Check if the List Contains an Element Scala Check if List Is Null or Empty Scala Check if List Contains Duplicates Scala Check if String Is Null or Empty Scala Check if Option Is None Scala Check Option Has Value Stack Implementation in Scala Queue Implementation in Scala Priority Queue Implementation in Scala Linked List Implementation in Scala Doubly Linked List Implementation in Scala Circular Linked List Implementation in Scala Binary Tree Implementation in Scala Bubble Sort Algorithm in Scala Selection Sort Algorithm in Scala Insertion Sort Algorithm in Scala Merge Sort Algorithm in Scala Quick Sort Algorithm in Scala Heap Sort Algorithm in Scala Shell Sort Algorithm in Scala Linear Search Algorithm in Scala Binary Search Algorithm in Scala

Comments

Post a Comment