Rebuilding Binary Tree from Preorder and Inorder Traversals

Buatlah pohon biner dari hasil preorder dan inorder di bawah ini:

Preorder	1	2	4	8	9	10	11	5	3	6	7
Inorder	8	4	10	9	11	2	5	1	6	3	7

Langkah 1

Kita bisa mengetahui dari soal di atas,bahwa yang akan menjadi root tertinggi adalah 1 (dengan menggunakan rumus Preorder dimana Root akan ditulis terlebih dahulu [root, left, right]),

Preorder	1	2	4	8	9	10	11	5	3	6	7
Inorder	8	4	10	9	11	2	5	1	6	3	7

maka kita bisa menggambar pohon kita sementara seperti ini:

binary tree tahap 1

Langkah 2

Kemudian, kita akan mengakses root yang kedua, yaitu 2 (sekali lagi, berdasarkan preorder)

Preorder	1	2	4	8	9	10	11	5	3	6	7
Inorder	8	4	10	9	11	2	5	1	6	3	7

Sehingga, gambar pohon kita menjadi seperti ini:

binary tree tahap 2

Langkah 3

Sama seperti proses sebelumnya, kita akan mengakses root yang selanjutnya, yaitu 4.Sehingga, gambar pohon kita akan menjadi seperti ini: 

Preorder	1	2	4	8	9	10	11	5	3	6	7
Inorder	8	4	10	9	11	2	5	1	6	3	7

binary tree tahap 3

Langkah 4

Jika di setiap kanan atau kiri dari root hanya terdapat satu deret node, maka ia akan langsung menjadi node child dari root tersebut (sebagai contoh angka 8 yang berada di sebelah kiri root 4, tidak memiliki node lainnya, sehingga secara otomatis, dia digambar sebagai node child nya). Maka untuk selanjutnya, kita akan langsung mengakses root berikutnya yaitu 9.

Preorder	1	2	4	8	9	10	11	5	3	6	7
Inorder	8	4	10	9	11	2	5	1	6	3	7

sehingga pohon biner kita akan menjadi seperti ini:

binary tree tahap 4

Langkah 5

Selesai dengan ruas kiri, sekarang kita beralih ke ruas kanan. Tabel preorder dan inorder terakhir adalah seperti di bawah ini, sehingga, root selanjutnya adalah 3, yang berada di ruas kanan.Sehingga pohon kita menjadi seperti ini: 

Preorder	1	2	4	8	9	10	11	5	3	6	7
Inorder	8	4	10	9	11	2	5	1	6	3	7

Dan penyelesaian pohon biner kita menjadi seperti ini:

binary tree tahap 5

source:http://crackinterviewtoday.wordpress.com/2010/03/15/rebuild-a-binary-tree-from-inorder-and-preorder-traversals
/