Oila daraxtini chizganingizni tasavvur qiling: har bir odamning ota-onasi bor, va har birining bolalari bo'lishi mumkin. Tree (daraxt) — aynan shunday tuzilma: bitta "ildiz" (root) bo'ladi, undan pastga "shoxlar" tarqaladi, har bir shox o'z "bolalari"ga ega bo'lishi mumkin.

Binary Tree (ikkilik daraxt) — bu daraxtning maxsus turi: har bir tugunning ko'pi bilan ikkita bolasi bo'ladi — "Left" (chap) va "Right" (o'ng). Agar bu ikkita bola ma'lum bir qoidaga bo'ysunsa (chap tomondagi hamma qiymat kichikroq, o'ng tomondagi hamma qiymat kattaroq bo'lsa), bu maxsus tur Binary Search Tree (BST, ikkilik qidiruv daraxti) deyiladi — va u ma'lumotni juda tez topish imkonini beradi.

package main

import "fmt"

type TreeNode struct {
	Value       int
	Left, Right *TreeNode
}

func (t *TreeNode) Insert(v int) *TreeNode {
	if t == nil {
		return &TreeNode{Value: v}
	}
	if v < t.Value {
		t.Left = t.Left.Insert(v)
	} else {
		t.Right = t.Right.Insert(v)
	}
	return t
}

func main() {
	var root *TreeNode
	for _, v := range []int{5, 3, 8, 1, 4} {
		root = root.Insert(v)
	}
	fmt.Println(root.Value, root.Left.Value, root.Right.Value)
}

Insert metodi qiziq bir usul bilan yozilgan: t *TreeNode bo'lsa-da, u nil bo'lishi ham mumkin (Go'da nil pointer'da metod chaqirish, ichida nil tekshiruvi bo'lsa, xavfsiz — buni "Pointers & Memory" kursida ko'rgan edingiz). Agar joriy tugun nil bo'lsa ("bu yerda hali hech kim yo'q"), yangi tugun shu yerda yaratiladi. Aks holda, qiymat kichikroq bo'lsa chap tomonga, kattaroq bo'lsa o'ng tomonga "yuborilib", o'sha yerda (rekursiv ravishda) xuddi shu jarayon takrorlanadi — toki bo'sh joy (nil) topilguncha.

Natijada daraxt o'z-o'zidan tartiblangan holga keladi: 5 ildiz bo'lib qoladi (birinchi qo'shilgan), 3 undan kichik bo'lgani uchun chapga, 8 kattaroq bo'lgani uchun o'ngga tushadi. 1 esa 5'dan kichik (chapga), so'ng 3'dan ham kichik (yana chapga) — shunday qilib 3'ning chap tomoniga joylashadi.