Pertanyaan & Jawaban Wawancara Pohon Biner Paling Umum [Untuk Freshers & Berpengalaman]

pengantar

Struktur data adalah salah satu konsep paling mendasar dalam pemrograman berorientasi objek. Untuk menjelaskannya secara sederhana, struktur data adalah cara tertentu untuk mengatur data di komputer sehingga dapat diproses secara efektif. Ada beberapa struktur data seperti tumpukan, antrian, dan pohon yang memiliki sifat uniknya sendiri.

Pohon memungkinkan kita untuk mengatur data secara hierarkis. Struktur data seperti itu sangat berbeda dari struktur data linier seperti daftar tertaut atau larik. Sebuah pohon terdiri dari node yang membawa informasi.

Pohon biner adalah jenis pohon khusus yang hanya dapat memiliki hingga dua anak. Ini berarti bahwa simpul tertentu dalam pohon biner tidak dapat memiliki anak, satu anak, atau dua anak tetapi tidak lebih. Pohon biner adalah struktur data penting yang memungkinkan kita memecahkan masalah yang sulit dan membangun kode yang kompleks.

Jika Anda melamar pekerjaan sebagai Pengembang Java atau insinyur perangkat lunak, wawancara Anda mungkin berisi beberapa pertanyaan seputar konsep ini. Seringkali, kandidat merasa sulit untuk menjawab pertanyaan berdasarkan pohon biner, pohon pencarian biner, dan program terkait. Pada artikel ini, kita akan mengeksplorasi beberapa pertanyaan wawancara yang paling sering diajukan terkait dengan pohon biner. Artikel ini akan membantu Anda lebih memahami konsep dan mempersiapkan Anda sehingga Anda bisa mendapatkan pekerjaan impian Anda!

Pertanyaan & Jawaban Wawancara Pohon Biner Teratas

Bagian berikut berisi katalog pertanyaan dan jawaban yang diharapkan berdasarkan konsep pohon biner.

1) Apa itu simpul daun?

Setiap simpul dalam pohon biner atau pohon yang tidak memiliki anak disebut simpul daun.

2) Apa itu simpul akar?

Node pertama atau node teratas dalam sebuah pohon disebut root node.

3) Bagaimana Anda menemukan leluhur bersama (LCA) terendah dari pohon biner di Jawa?

Mari kita pertimbangkan dua node n1 dan n2 yang merupakan bagian dari pohon biner.

Common ancestor (LCA) terendah dari n1 dan n2 adalah shared ancestor dari n1 dan n2 yang terletak paling jauh dari root.

Anda dapat mengikuti metode berikut untuk menemukan LCA.

1. a) Temukan jalur dari simpul akar ke n1 dan simpan dalam larik.
2. b) Temukan jalur dari simpul akar ke n2 dan simpan dalam larik.
3. c) Lintasi kedua jalur hingga nilainya sama di kedua array.

4) Bagaimana Anda memeriksa apakah pohon biner yang diberikan adalah subpohon dari pohon biner lain?

Anggap kita memiliki pohon biner T. Sekarang kita ingin memeriksa apakah pohon biner S adalah subpohon dari T.

Untuk melakukan ini, pertama, coba periksa apakah Anda menemukan simpul di T yang juga ada di S.

Setelah Anda menemukan simpul umum ini, periksa apakah simpul berikut juga merupakan bagian dari S.

Jika ya, kita dapat dengan aman mengatakan bahwa S adalah subpohon dari T.

Harus Dibaca: Ide & Topik Proyek Struktur Data

5) Bagaimana Anda menemukan jarak antara dua node di pohon biner?

Pertimbangkan dua node n1 dan n2 yang merupakan bagian dari pohon biner.

Jarak antara n1 dan n2 sama dengan jumlah minimum edge yang harus dilalui untuk mencapai dari satu node ke node lainnya.

Penting untuk dicatat bahwa Anda melintasi jarak terpendek antara node.

6) Apa itu pohon pencarian biner?

Pohon pencarian biner (BST) adalah jenis pohon biner khusus di mana setiap simpul internal berisi kunci. Untuk pohon pencarian biner, aturannya adalah:

1. a) Sebuah node dapat memiliki kunci yang lebih besar dari semua kunci di subtree kiri node.
2. b) Sebuah node dapat memiliki kunci yang lebih kecil dari semua kunci di subtree kanan node.

Jadi, jika n1 adalah simpul yang memiliki kunci 8, maka setiap simpul di subpohon kiri n1 akan berisi kunci yang lebih kecil dari 8, dan setiap simpul di subpohon kanan n1 akan berisi kunci yang lebih besar dari 8.

7) Apa itu pohon keseimbangan diri?

Pohon pencarian biner self-balanced secara otomatis menjaga ketinggiannya sekecil mungkin ketika operasi seperti penyisipan dan penghapusan berlangsung.

Agar BST menjadi self-balance, penting untuk mengikuti aturan BST secara konsisten sehingga subpohon kiri memiliki kunci bernilai lebih rendah sedangkan subpohon kanan memiliki kunci bernilai tinggi.

Ini dilakukan dengan menggunakan dua operasi:

– Rotasi kiri

– Rotasi kanan

8) Apa itu pohon AVL?

Pohon AVL dinamai menurut penemunya: Adelson, Velski, dan Landis. Pohon AVL adalah pohon biner self-balancing yang memeriksa ketinggian subpohon kiri dan subpohon kanannya dan memastikan bahwa perbedaannya tidak lebih dari 1. Perbedaan ini disebut faktor keseimbangan

Jadi, BalanceFactor = tinggi (Subpohon kiri) – tinggi (Subpohon kanan)

Jika faktor keseimbangan lebih dari 1, pohon diseimbangkan menggunakan beberapa teknik berikut:

– Rotasi kiri

– Rotasi kanan

– Rotasi Kiri-Kanan

– Rotasi Kanan-Kanan

Baca Juga: Pengurutan dalam Struktur Data

9) Bagaimana Anda mengubah pohon biner menjadi pohon pencarian biner di Jawa?

Perbedaan utama antara pohon biner dan pohon pencarian biner adalah bahwa BST mengikuti subpohon kiri harus memiliki nilai kunci yang lebih rendah dan subpohon kanan harus memiliki aturan nilai kunci yang lebih tinggi. Hal ini dapat dilakukan dengan menggunakan serangkaian teknik traversal sebagai berikut:

1. Buat array sementara yang menyimpan traversal inorder dari pohon
2. Urutkan array sementara. Anda dapat menggunakan algoritma pengurutan apa pun di sini.
3. Sekali lagi lakukan traversal inorder pada pohon.
4. Salin elemen array satu per satu ke setiap simpul pohon.

10) Bagaimana Anda menghapus simpul dari pohon pencarian biner di Jawa?

Operasi penghapusan untuk BST bisa menjadi rumit karena propertinya perlu dipertahankan setelah operasi. Berikut ini adalah tiga kemungkinan kasus:

1. Node yang akan dihapus adalah node daun.
   Cukup hapus simpulnya.
2. Node yang akan dihapus memiliki satu anak.

Dalam hal ini, salin anak ke simpul dan hapus anak.

1. Node yang akan dihapus memiliki dua anak.

Dalam hal ini, temukan penerus terurut dari simpul tersebut. Anda kemudian dapat menyalin kontennya ke node dan menghapus penerus inorder.

11) Apa struktur data pohon Merah-Hitam?

Pohon Merah-Hitam adalah jenis khusus dari pohon penyeimbang diri yang memiliki sifat-sifat sebagai berikut:

1. Setiap node memiliki warna merah atau hitam.
2. Akarnya selalu hitam.
3. Node merah tidak dapat memiliki orang tua merah atau anak merah.
4. Setiap jalur dari simpul akar ke simpul NULL memiliki jumlah simpul hitam yang sama.

Harus Dibaca: Ide & Topik Proyek Struktur Data

12) Bagaimana Anda menemukan jika dua pohon identik?

Dua pohon biner identik jika memiliki data dan susunan yang sama. Ini dapat dilakukan dengan melintasi kedua pohon dan membandingkan data dan pengaturannya.

Inilah algoritme yang memungkinkan kita melakukan ini:

1. Periksa data simpul akar ( data pohon1 == data pohon2)
2. Periksa subtree kiri secara rekursif. panggil sameTree( tree1-> subtree kiri, tree2-> subtree kiri)
3. Demikian pula, periksa subpohon kanan
4. jika a,b,c benar, kembalikan1

Checkout: Jenis Pohon Biner

Pikiran Akhir

Pada artikel ini, kami menjelajahi beberapa pertanyaan wawancara pohon pencarian biner yang paling sering ditanyakan. Menjelajahi lebih banyak tentang struktur data dapat membantu Anda memahami logika dan pemrograman dengan lebih baik. Anda dapat mencoba melihat contoh yang disebutkan dalam artikel ini dan berlatih dengan mengubah nilai untuk membangun dasar Anda. Dengan beberapa latihan, Anda akan berada dalam posisi yang bagus untuk memecahkan wawancara Anda.

Jika Anda penasaran untuk belajar tentang ilmu data, lihat Program PG Eksekutif IIIT-B & upGrad dalam Ilmu Data yang dibuat untuk para profesional yang bekerja dan menawarkan 10+ studi kasus & proyek, lokakarya praktis, bimbingan dengan pakar industri, 1 -on-1 dengan mentor industri, 400+ jam pembelajaran dan bantuan pekerjaan dengan perusahaan-perusahaan top.