A collection of programming challenges

BinarySearchTree.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BinarySearchTree {
  Scanner console = new Scanner(System.in);
  Node root;

  public static void main(String[] args) throws Exception {
    BinarySearchTree program = new BinarySearchTree();
    program.runMenu();
  }

  private void runMenu() {
    while (true) {
      System.out.println("\n-----------------------------------------");
      System.out.println("Binary Search Tree Interactive Menu");
      System.out.println("a) Insert");
      System.out.println("b) Search");
      System.out.println("c) Print");
      System.out.println("d) Reset");
      System.out.println("e) Exit");

      System.out.print("\nSelect an action: ");
      String choice = console.nextLine();

      switch (choice.toLowerCase()) {
        case "a":
          insert();
          break;
        case "b":
          search();
          break;
        case "c":
          print();
          break;
        case "d":
          reset();
          break;
        case "e":
          exit();
          break;
        default:
          System.out.println("Invalid choice. Try again.");
          break;
      }
    }
  }

  private void insert() {
    System.out.print("Enter a list of numbers (separated by space): ");
    String[] numbers = console.nextLine().split(" ");
    for (String number : numbers) {
      int value = Integer.parseInt(number);
      if (root == null) {
        root = new Node(value);
      } else {
        root.insert(value);
      }
    }
  }

  private void search() {
    if (root == null) {
      System.out.println("Tree is empty.");
      return;
    }

    System.out.print("Enter a number to search: ");
    int value = Integer.parseInt(console.nextLine());

    if (!root.contains(value)) {
      System.out.println("Value not found.");
      return;
    }

    Node node = root;
    while (node.data != value) {
      if (value < node.data)
        node = node.left;
      else
        node = node.right;
    }

    printTree(node);
  }

  private void print() {
    if (root == null) {
      System.out.println("Tree is empty.");
      return;
    }
    printTree(root);
  }

  private void reset() {
    root = null;
    System.out.println("Tree has been reset.");
  }

  private void exit() {
    System.out.println("Exiting...");
    System.exit(0);
  }

  // BINARY TREE PRINTING
  private void printTree(Node node) {
    System.out.println("\n-----------------------------------------");
    System.out.println("\nVisual Tree: ");
    System.out.println(node.printNode());

    System.out.println("\nPre-Order (TLF) ");
    printPreOrder(node);

    System.out.println("\n\nIn-Order (LTF) ");
    printInOrder(node);

    System.out.println("\nPost-Order (LFT) ");
    printPostOrder(node);
    System.out.println();
  }

  private void printInOrder(Node node) {
    if (node.left != null)
      printInOrder(node.left);
    if (node.right != null)
      printInOrder(node.right);
  }

  private void printPreOrder(Node node) {
    System.out.print(node.data + " ");
    if (node.left != null)
      printPreOrder(node.left);
    if (node.right != null)
      printPreOrder(node.right);
  }

  private void printPostOrder(Node node) {
    if (node.left != null)
      printPostOrder(node.left);
    if (node.right != null)
      printPostOrder(node.right);
    System.out.print(node.data + " ");
  }

  // BINARY TREE NODE
  public class Node {
    int data;
    Node left;
    Node right;
    int padding = 1;

    public Node(int data) {
      this.data = data;
    }

    public void insert(int value) {
      if (value <= data) {
        if (left == null)
          left = new Node(value);
        else
          left.insert(value);
      } else {
        if (right == null)
          right = new Node(value);
        else
          right.insert(value);
      }
    }

    public boolean contains(int value) {
      if (value == data)
        return true;
      if (value < data && left != null)
        return left.contains(value);
      if (value > data && right != null)
        return right.contains(value);
      return false;
    }

    private int indent(List<String> lines, int margin) {
      if (margin >= 0)
        return margin;
      String spaces = " ".repeat(-margin);
      for (int i = 0; i < lines.size(); i++)
        lines.set(i, spaces + lines.get(i));
      return 0;
    }

    private List<String> merge(List<String> left, List<String> right) {
      int minSize = Math.min(left.size(), right.size());
      int offset = 0;
      for (int i = 0; i < minSize; i++)
        offset = Math.max(offset, left.get(i).length() + padding - right.get(i).replaceAll("\\S.*", "").length());
      indent(right, -indent(left, offset));
      for (int i = 0; i < minSize; i++)
        left.set(i, left.get(i) + right.get(i).substring(left.get(i).length()));
      left.addAll(right.subList(minSize, right.size()));
      return left;
    }

    private List<String> buildLines(Node node) {
      if (node == null)
        return new ArrayList<>();
      List<String> lines = merge(buildLines(node.left), buildLines(node.right));
      int half = String.valueOf(node.data).length() / 2;
      int i = half;
      if (lines.size() > 0) {
        String line;
        i = lines.get(0).indexOf("*");
        if (node.right == null) {
          line = " ".repeat(i) + "┌─┘";
          i += 2;
        } else if (node.left == null) {
          line = " ".repeat(i = indent(lines, i - 2)) + "└─┐";
        } else {
          int dist = lines.get(0).length() - 1 - i;
          line = String.format("%s┌%s┴%s┐", " ".repeat(i), "─".repeat(dist / 2 - 1), "─".repeat((dist - 1) / 2));
          i += dist / 2;
        }
        lines.set(0, line);
      }
      lines.add(0, " ".repeat(indent(lines, i - half)) + node.data);
      lines.add(0, " ".repeat(i + Math.max(0, half - i)) + "*");
      return lines;
    }

    public String printNode() {
      return String.join("\n", buildLines(this).subList(1, buildLines(this).size()));
    }
  }
}