Pertanyaan ini cukup banyak menjelaskan bahwa mereka bisa, tetapi tidak menunjukkan contoh ada dua pohon yang berbeda dengan traversal pre-order yang sama.

Disebutkan pula bahwa traversal berurutan dari dua pohon yang berbeda dapat sama meskipun secara struktural berbeda. Apakah ada contohnya?

Contoh Pohon (gambar) :

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /  
 3   

Ini adalah contoh yang sesuai dengan skenario Anda, nilai akar pohon 1 adalah 1, memiliki anak kiri dengan nilai 2, dan anak kirinya juga anak kiri dengan nilai 3.

Nilai akar pohon B adalah 1, memiliki anak kiri dengan nilai 2 dan anak kanan dengan nilai 3.

Dalam kedua kasus, Preorder traversal adalah 1-> 2-> 3.

$n$$n$$1,2,\dots,n$

Ini berarti bahwa kita dapat menamai node dari struktur pohon biner apa pun sehingga akan menghasilkan urutan pre-order yang sama dengan yang ada pada pohon lain.

Ini tidak akan berfungsi jika kita harus mengasumsikan properti lain dari pohon. Sebagai contoh, jika pohon seharusnya pohon pencarian biner, dengan semua kunci berbeda, urutan pre-order-nya akan secara unik menentukan pohon.

Menghitung argumen

$n$$n^\text{th}$$C_n=(2n)!/(n!(n+1)!).$

    o         o         o         o         o
   /         /         / \         \         \
  o         o         o   o         o         o      .
 /           \                     /           \
o             o                   o             o

$n!$

$n!$$n$$n!$$C_n>1$$n>1.$$n$

Mengenai pertanyaan kedua Anda, ya dua pohon yang berbeda secara struktural dapat memiliki inorder traversal yang sama. Salah satu contohnya adalah:

     A:                 B:

     1                  2
    / \                  \
   2   3                  1
                           \
                            3

Inorder traversal kedua pohon sama. 2 -> 1 -> 3