How to Convert a BST to a Doubly Linked List In-Place

Problem:
Convert a BST to a doubly-linked list in-place. Think of the left and right pointers as synonymous to the previous and next pointers in a doubly-linked list.

package main

import (
    "fmt"
)

type Node struct {
    Value int
    Left  *Node
    Right *Node
}

type LinkedList struct {
    Front *Node
    Back  *Node
}

// this is the actual algorithm that converts a BSt into a doubly linked list
// the rest of the code is just to make unit testing easier
func (l *LinkedList) ToLinkedList(node *Node) {
    if node == nil {
        return
    }
    l.ToLinkedList(node.Left)
    node.Left = l.Back
    if l.Back != nil {
        l.Back.Right = node
    } else {
        l.Front = node
    }
    l.Back = node
    l.ToLinkedList(node.Right)
}

type BST struct {
    Root *Node
}

func (b *BST) Add(value int) {
    b.Root = b.add(b.Root, value)
}

func (b *BST) add(node *Node, value int) *Node {
    if node == nil {
        return &Node{value, nil, nil}
    }
    if node.Value > value {
        node.Left = b.add(node.Left, value)
    } else if node.Value < value {
        node.Right = b.add(node.Right, value)
    }
    return node
}

func main() {
    values := []int{8, 3, 10, 1, 6, 14, 4, 7, 13}
    bst := BST{}
    for _, v := range values {
        bst.Add(v)
    }
    ll := LinkedList{}
    ll.ToLinkedList(bst.Root)
    for n := ll.Front; n != nil; n = n.Right {
        fmt.Print(n.Value, " ")
    }
    fmt.Println()
    for n := ll.Back; n != nil; n = n.Left {
        fmt.Print(n.Value, " ")
    }
    fmt.Println()
}

Output:

1 3 4 6 7 8 10 13 14 
14 13 10 8 7 6 4 3 1

How to Force Kill a Process in Java

In Java, there is no easy way to force a termination of a process spawned in Java. Calling Process.destroy() does not guarantee that the process will be terminated. Although Java 8 might fix this with Process.destroyForcibly(), if you still use older versions of Java, you are out of luck. Below is a not-so-portable solution to terminate a process on Linux and Windows using Java Native Runtime. You could also use JNA or JNI to invoke the OS native API.

package test;

import java.lang.reflect.Field;

import jnr.ffi.LibraryLoader;
import jnr.ffi.Pointer;
import jnr.ffi.Runtime;

public class Test {
    public static interface Kernel32 {
        boolean TerminateProcess(Pointer handle, int exitCode);
    }
    
    public static interface Posix {
        int kill(int pid, int sig);
    }
    
    public static void main(String[] args) throws Exception {
        ProcessBuilder pb = new ProcessBuilder(args[0]);
        Process p = pb.start();
        System.out.println("Sleeping for 5 seconds");
        Thread.sleep(5000);
        p.destroy();
        if (System.getProperty("os.name").toLowerCase().startsWith("win")) {
            if (p.getClass().getName().equals("java.lang.Win32Process") ||
                p.getClass().getName().equals("java.lang.ProcessImpl")) {
                Field f = p.getClass().getDeclaredField("handle");
                f.setAccessible(true);
                long handle = f.getLong(p);
                
                System.out.println("Killing process");
                Pointer ptr = Pointer.wrap(Runtime.getSystemRuntime(), handle);
                int exitCode = 0;
                Kernel32 kernel32 = LibraryLoader.create(Kernel32.class).load("Kernel32");
                kernel32.TerminateProcess(ptr, exitCode);
            }
        } else {
            if (p.getClass().getName().equals("java.lang.UNIXProcess")) {
                Field f = p.getClass().getDeclaredField("pid");
                f.setAccessible(true);
                int pid = f.getInt(p);
                
                System.out.println("Killing process");
                Posix posix = LibraryLoader.create(Posix.class).load("c");
                posix.kill(pid, 9);
            }
        }
    }
}