最も一般的な二分木インタビューの質問と回答[新入生と経験者向け]

序章

データ構造は、オブジェクト指向プログラミングの最も基本的な概念の1つです。 簡単に説明すると、データ構造は、データを効果的に処理できるようにコンピューター内でデータを編成する特定の方法です。 スタック、キュー、ツリーなど、独自のプロパティを持つデータ構造がいくつかあります。

ツリーを使用すると、データを階層的に整理できます。 このようなデータ構造は、リンクリストや配列などの線形データ構造とは大きく異なります。 ツリーは、情報を運ぶノードで構成されています。

二分木は、最大2つの子を持つことができる特殊なタイプのツリーです。 つまり、バイナリツリーの特定のノードには、子を持たない、1つの子、または2つの子を含めることができますが、それ以上にすることはできません。 二分木は、難しい問題を解決し、複雑なコードを構築することを可能にする重要なデータ構造です。

Java開発者またはソフトウェアエンジニアとしての仕事に応募する場合、面接にはこの概念を中心としたいくつかの質問が含まれる場合があります。 多くの場合、候補者は、二分木、二分探索木、および関連するプログラムに基づいて質問に答えるのが難しいと感じます。 この記事では、二分木に関連する最もよくあるインタビューの質問のいくつかを探ります。 この記事は、概念をよりよく理解し、夢の仕事に着手できるように準備するのに役立ちます。

トップ二分木インタビューの質問と回答

次のセクションには、二分木の概念に基づいた質問とその予想される回答のカタログが含まれています。

1）リーフノードとは何ですか？

二分木または子を持たないツリー内のノードは、リーフノードと呼ばれます。

2）ルートノードとは何ですか？

ツリーの最初のノードまたは最上位ノードは、ルートノードと呼ばれます。

3）Javaでバイナリツリーの最も低い共通祖先（LCA）をどのように見つけますか？

二分木の一部である2つのノードn1とn2を考えてみましょう。

n1とn2の最も低い共通祖先（LCA）は、ルートから最も遠い位置にあるn1とn2の共有祖先です。

次の方法でLCAを見つけることができます。

1. a）ルートノードからn1へのパスを見つけて、配列に格納します。
2. b）ルートノードからn2へのパスを見つけて、配列に格納します。
3. c）値が両方の配列で同じになるまで、両方のパスをトラバースします。

4）特定の二分木が別の二分木のサブツリーであるかどうかをどのように確認しますか？

二分木Tがあるとします。次に、二分木SがTのサブツリーであるかどうかを確認します。

これを行うには、まず、SにもあるノードがTにあるかどうかを確認してみてください。

この共通ノードを見つけたら、次のノードもSの一部であるかどうかを確認します。

はいの場合、SはTのサブツリーであると安全に言うことができます。

必読：データ構造プロジェクトのアイデアとトピック

5）二分木の2つのノード間の距離をどのように見つけますか？

二分木の一部である2つのノードn1とn2について考えてみます。

n1とn2の間の距離は、1つのノードから別のノードに到達するためにトラバースする必要があるエッジの最小数に等しくなります。

ノード間の最短距離をトラバースすることに注意することが重要です。

6）二分探索木とは何ですか？

二分探索木（BST）は、各内部ノードにキーが含まれる特殊なタイプの二分木です。 二分探索木の場合、ルールは次のとおりです。

1. a）ノードは、ノードの左側のサブツリーにあるすべてのキーよりも大きいキーを持つことができます。
2. b）ノードは、ノードの右側のサブツリーにあるすべてのキーよりも小さいキーを持つことができます。

したがって、n1がキー8を持つノードである場合、n1の左側のサブツリーのすべてのノードには8未満のキーが含まれ、n1の右側のサブツリーのすべてのノードには8より大きいキーが含まれます。

7）自己平衡木とは何ですか？

自己平衡二分探索木は、挿入や削除などの操作が行われるときに、自動的に高さを可能な限り小さく保ちます。

BSTが自己平衡化されるためには、BSTの規則に一貫して従い、左側のサブツリーが低い値のキーを持ち、右側のサブツリーが高い値のキーを持つようにすることが重要です。

これは、次の2つの操作を使用して実行されます。

–左回転

–右回転

8）AVLツリーとは何ですか？

AVLツリーは、その発明者であるAdelson、Velski、Landisにちなんで名付けられました。 AVLツリーは、左側のサブツリーと右側のサブツリーの高さをチェックし、差が1以下であることを保証する自己平衡二分木です。この差はバランス係数と呼ばれます。

したがって、BalanceFactor = height（左のサブツリー）– height（右のサブツリー）

バランス係数が1より大きい場合、ツリーは次の手法のいくつかを使用してバランスが取られます。

–左回転

–右回転

–左右回転

–右-右回転

また読む：データ構造での並べ替え

9）Javaでバイナリツリーをバイナリ検索ツリーに変換するにはどうすればよいですか？

二分木と二分探索木の主な違いは、BSTが左側のサブツリーに続くキー値は低く、右側のサブツリーは高いキー値のルールに従う必要があることです。 これは、次のような一連のトラバーサル手法を使用して実行できます。

1. ツリーの順序どおりの走査を格納する一時配列を作成します
2. 一時配列をソートします。 ここでは、任意の並べ替えアルゴリズムを使用できます。
3. 再度、ツリーで順序どおりの走査を実行します。
4. 配列要素を1つずつ各ツリーノードにコピーします。

10）Javaのバイナリ検索ツリーからノードを削除するにはどうすればよいですか？

BSTの削除操作は、操作後にそのプロパティを保持する必要があるため、注意が必要な場合があります。 考えられる3つのケースすべてを見てみましょう。

1. 削除するノードはリーフノードです。
   ノードを削除するだけです。
2. 削除するノードには子が1つあります。

この場合、子をノードにコピーし、子を削除します。

1. 削除するノードには2つの子があります。

この場合、ノードの順序の後続を見つけます。 次に、そのコンテンツをノードにコピーして、インオーダーサクセサを削除できます。

11）赤黒木データ構造とは何ですか？

赤黒木は、次のプロパティを持つ特殊なタイプの自己平衡ツリーです。

1. 各ノードの色は赤または黒です。
2. ルートは常に黒です。
3. 赤いノードは、赤い親または赤い子を持つことはできません。
4. ルートノードからNULLノードへのすべてのパスには、同じ数のブラックノードがあります。

必読：データ構造プロジェクトのアイデアとトピック

12）2本の木が同一であるかどうかをどのように見つけますか？

2つの二分木は、同じデータと配置を持っている場合は同一です。 これは、両方のツリーをトラバースし、それらのデータと配置を比較することで実行できます。

これを可能にするアルゴリズムは次のとおりです。

1. ルートノードのデータを確認します（tree1 data == tree2 data）
2. 左のサブツリーを再帰的にチェックします。 sameTree（tree1->左サブツリー、tree2->左サブツリー）を呼び出す
3. 同様に、右のサブツリーを確認してください
4. a、b、cが真の場合、return1

チェックアウト：二分木の種類

最終的な考え

この記事では、最もよく聞かれる二分探索木インタビューの質問のいくつかを調査しました。 データ構造について詳しく調べると、ロジックとプログラミングをよりよく理解するのに役立ちます。 この記事で言及されている例を見て、値を変更して基本を構築することで練習することができます。 ある程度の練習をすれば、面接をクラックするのに最適な立場になります。

データサイエンスについて知りたい場合は、IIIT-B＆upGradのデータサイエンスのエグゼクティブPGプログラムをチェックしてください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界の専門家とのメンターシップを提供します。1業界のメンターとの1対1、400時間以上の学習、トップ企業との仕事の支援。