二分木とはひとつの親に対してふたつの子が対応付けられているデータ構造である． 二分木はノードと呼ぶデータ構造をつなぎ合わせることで実現することができる． ノードは各要素のデータ(例えば整数)とふたつの子のノードが何かを示す情報で構成される．
このノードを複数接続し，頂点のノード(これを根という)を記憶することで二分木を構成することができる． 二分木の任意のノード以下の部分に着目すると，これもまた二分木である．これを部分木という．二分探索木とはすべてのノードについて以下の条件を満たす二分木である．