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.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

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.

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

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);             }         }     } }