CP #45: Binary Tree Problemleri 1

Binary Tree

Birkac noktayi hatirlatalim:

Her bir node sadece tek bir parent'e sahiptir. Bazi implementasyonlarda node icinde parent bilgisi de tutulmaktadir. Bu sayede time ve space compl. azaltilabilir. Akilda tutmakta yarar var.
Search path: Tree'nin root node'undan, bir node kadar olan cizgi uzerindeki node'lardan olusan sequence'a o node'un search path'i adi verilir.
Bir node'un search path'inda bulunan tum node'lar, o node'un ancestor (atasi) olarak tanimlanir.
Bir node'un da altinda bulunan tum node'lar descendant olarak adlandirilir.
Full binary tree: Leaf node'lar haric tum node'lari 2 eleman iceren binary treedir
Perfect binary tree: Tum node'lari 2 child iceren ve tum leaf node'larin depth degeri esit olan, yani kisaca full + full binary treedir.

2^(h+1)-1 node icermektedir ki h, full bintree'nin yuksekligidir.
verilen h yuksekligi icin bir full bintree, log(h) eleman icermektedir.
2^h kadar leaf node icermektedir

Traversal

Inorder, preorde ve postorder olmak uzere 3 temel traversal (walking) yontemi vardir.
Tumu O(n) time compl. sahiptir. (her bir node 1 kere ziyaret ediliyor kabulu ile)
Ekstra space kullanilmamis gibi gozukse de, genellik binary tree traversal islemleri recursive olarak yapilmaktadir. Bu durumda, tree yuksekligi kadar ayni forknsiyon ust uste cagrildigi icin (recursive olarak), sistem call-stack'inde bunlarin bilgisi tutulmasi gerekir. Dolayisi ile h yuksekliginde bir binary tree, O(h) kadar ek bir space gereksinimi getirmektedir.
eger tree balanced ise O(h) -> O(log n)'e tekabul eder [Best case]
eger tree skewed ise O(h) -> O(n)'e tekabul eder [Worst case]

1. Test If a Binary Tree Is Height Balanced

Bir binary tree'de her bir node'un solundaki ve sagindaki binary tree'lerin yukseklikleri arasindaki fark en fazla 1 ise, buna height balanced binary tree adi verilir. Binary tree'nin root node'unu arguman olarak alan ve height-balanced olup olmadigini kontrol eden bir program yaziniz.

Cozum

Bizden istenen her bir node'un solundaki ve sagindaki binary tree'lerin kontrol edilmesi. Yani, root'tan leaf nodelara kadar gitmesi gereken bir is.

Left node'lari balanced saymak mantikli olur. Ne de olsa sol ve sag agaclarin yukseklikleri ayni (yoklar). Hatta, leaf node'un null olan sol ve sag node'larinin yukseklik degeri -1 kabul edersek eger, genel bir formulle herhangi bir node'un rootu oldugu sub-binary tree'nin yuksekligini soyle hesaplayabiliriz:

height = max(left_height, right_height) + 1

Bir node icin height degerini hesaplayabiliyoruz, guzel. Root node'dan baslayarak recursive olarak en alt node'lara indik diyelim. Her bir ust node'a ciktigimizda egere alt node'lardaki height degerlerini bir yerde tutmaz isek, tekrar tekrar hesaplamak gerekecektir. Ornek:

2 3

4 n n 5

(n'ler null bu arada). Gibi bir tree icin, 2 node'unu ele alalim. Sol agac 0 yuksekliginde, sag agac da -1 yuksekliginde (cunku yok). Demek ki burasi balanced (aradaki fark max 1 olmasi gerekiyordu).

Ancak bir ust node'a ciktigimizda, yani 1'i incelerken, yine sol ve sag agaclarin yuksekliklerini bulmamiz gerekiyor ki balanced olup olmadigini anlayabilelim. Bunu yapamayiz.

Diger bir secenek, 2'de hesapladigimiz yukseklik degerini, node'un icinde baska bir alanda tutmak. Yani BinaryTreeNode class'ina ek yapmamiz gerek. Bu da ek bir space maliyeti getirecek tabi.

Diger bir secenek ise, her bir iterasyon adiminda, inceledigimiz node icin toplam yukseklik degerini ve de balanced olup olmadigini ayni anda dordurmek. Bu sayede 2 node'unu inceledikten sonra, geriye hem bu sub-tree'nin balanced oldugu bilgisini hem de yuksekliginin 1 oldugu bilgisini dondurursek, 1 node'u islerken cok rahat ederiz. Ve de ekstra space maliyetinden kurtulmus oluruz.

Ayni anda birden fazla deger dondurmek icin yeni bir class olusturabilir, named tuple kullanabilir ya da sadece tuple dondurebiliriz.

def is_tree_balanced(tree: BinaryTreeNode) -> bool:

def is_node_balanced(node):

# egere bir leaf node'un altinda bulunan None degerine denk geldiysek

# yukarida bahsettigimiz gibi balanced=True ve yukseklik = -1 donduruyoruz

if not node:

return (True, -1)

# sol sub-tree'ye bir bakalim

left = is_node_balanced(node.left)

# eger sol sub-tree balanced degil ise

# daha fazla devam etmeye gerek yok

# bu sonucu direk dondurelim ki,

# bu fonksyion ilk cagrildigi yere tekrar geri donsun

if not left[0]:

return left # unutmamak lazim ki burada tuple donduruyoruz

# simdi ayni sekilde sag tarafa bakalim

right = is_node_balance(node.right)

if not right[0]:

return right

# bu noktada sol ve sag taraflar balanced

# peki node'un kendisi balanced mi?

# sol ve sag taraf icin height degerlerini de

# bildigimize gore kolayca hesaplayabiliriz

is_balanced = abs(left[1], right[1]) <= 1

# peki bu node'un, root oldugu sub-tree'nin

# yuksekligi nedir?

h = max(left[1], right[1]) + 1

# bu node icin balanced bilgisi ve

# toplam yukseklik degerini donduruyoruz

return (is_balanced, h)

# recursive fonksyonimuzu root icin calistiriyoruz

# burada bize yine tuple donecek ve ilk eleman

# tree'nin balanced olup olmadigi bilgisi

return is_node_balanced(tree)[0]

Bakacak olursak post-order traversal yapiyoruz. Zaman maliyeti O(n). Space maliyeti sadece recursive fonksiyondan gelen call-stack maliyeti ki bu da tree'nin balanced olmadigi anda sonlaniyor. Upper-bound olarak tree'nin yuksekligi alinabilir O(h).

2. Test If A Binary Tree Is Symmetric

Verilen bir binary tree'nin simetrik olup olmadigini kontrol eden bir program yaziniz. Simetrik binary tree, root'tan bir duz cizgi cektigimizde sol ve sag sub-tree'lerin birbirinin simetrigi olmasi durumudur.

Cozum

Benim aklime ilk gelen cakal yontem, tree'yi inonder traversal yaparak bir arraya donusturmek ve bu array simetrik mi degil mi diye bir dongu ile bastan ve sondan ilerlerleyerek kontrol etmekti. Ancak bazi edce case'lerde basariz oluryor bu yontem.

Root'tan baslayarak bakacak olursak, nasil bu kontrolu yapariz?

1. Verilen root'un sol ve sag node'larinin degerleri ayni olmali

2. Rootun sol sub-tree'si, sag sub-tree'si ile simetrik olmali

Bu bize bir recursion isaret ediyor. Her bir node'un sol ve sag sub-tree'lerini recursive olarak simetriklik kontrolu yapabiliriz.

def is_tree_symmetric(tree):

def check_symmetry(subtree1, subtree2):

# eger iki taraf da None ise, leaf node demektir ve

# simetrik kabul ederiz

if not subtree1 and not subtree2:

return True

# eger iki taraf ta var ise,

# degerleri ve de onlarin da sol-sag sub-trelerini kontrol etmeliyiz

elif subtree1 and subtree2:

return (subtree1.data == subtree2.data and

check_symmetry(subtree1.left, subtree2.right) and

check_symmetry(subtree1.right, subtree2,left))

# son secenek ise bir taraf None diger taraf None degil

# bu durumda simetri bozuluyor

return False

# eger tree, None ise simetrik kabul edebiliriz

if not tree: return True

# ve de recursive kontrolumuzu root node'dan baslatiyoruz

return check_symmetry(root.left, root.right)

Analizini yapacak olur ise, recursive olarak tum tree node'larini sadece tek bir seferde dolasiyoruz, O(n) time compl. tekabul ediyor. Ekstra memory olarak da sadece recursion'dan dolayi kullanilan call stack var ki bu da tree yuksekligine bagli, O(h) diyebiliriz.

3. Compute The Lowest Common Ancestor In A Binary Tree

Binary tree icerisinde herhangi iki node icin, kendilerine en yakin ancestor'a LCA adi verilmektedir.

Ornegin burada 7 ve 6'nin LCA'i 5 olarak gorulmektedir.

Verilen bit binary tree ve iki node icin, LCA hesaplayan bir algoritma tasarlayiniz.

Cozum

Ilk akla gelen naive cozum ile basliyoruz. Verilen iki node icin, roottan baslayarak pathini cikartsak, ve bu pathleri karsilastirip, ilk ortak noktasini bulsak, bu nokta LCA olacaktir.

Yani soyle, yukaridaki ornekte 7 icin,

path_7 = [3, 5, 2, 7] ve 6 icin

path_6 = [3, 5, 6]

Goruldugu gibi bu path'leri sondan baslyarak karsilastirirsak, bir noktada bu pathler kesisecektir. Bu nokta da LCA olacaktir.

def lowest_common_ancestor(tree, node0, node1):

# path'leri hesaplayacak DFS fonksiyonumuz

def dfs(node, target, path):

# eger leaf node'a geldi isek, bos array dondur.

# cunku ileride recursive call'lardan gelen tum sonuclari

# birlestirecegiz.

if not node:

return []

# eger mevcut node'un datasi aradimiz deger ise

# path burada bitiyor

# dikkat edelim ki burada path'i olustururken data'lari degil de

# node'larin kendilerini tutuyoruz. Cunku LCA bizden tree node

# olarak isteniyor.

elif node.data == target:

return path + [node]

# eger henuz hedefe ulasamadi isek

# sol ve sag sub-tree'lerden devam ediyoruz

return dfs(node.left, target, path + [node]) + \

dfs(node.right, target, path + [node])

# simdi pathleri olusturalim

path0 = dfs(tree, node0.data, [])

path1 = dfs(tree, node1.data, [])

# path karsilastirmasi ve LCA bulma

# LCA garanti oldugu icin (en kotu ihtimal root node'dur)

# burada sonsuz dongu bile kullanabiliriz

i = -1

while True:

# degerler esit ise LCA'yi bulduk

if path0[i].data == path1[i].data:

return path0[i]

i -= 1

Analiz edecek olur isek iki kere DFS yapiyoruz. Ver herbir DFS ne yazikki O(n) maliyete sahip, cunku array concat islemi yapiyoruz. Bu durumda O(n^2) gibi bir toplam time compl. elde etmis oluyoruz.

Ekstra memory ise, iki adet path degeri tutuyoruz. Onemli nokta su ki, path icerisindeki her bir eleman, tree'nin bir level'inden geliyor. Yani ayni levelden 2 eleman gelemez. Bu acidan upper limit tree'nin yuksekligidir, yani O(h). Iki tane path degeri ve de call stack'ten gelen O(h) ile birlikte toplamda O(3*h) yani O(h) ekstra memory kullanmis durumdayiz.

Bir baska yaklasim ise, yine recursive olarak her bir sub-tree analiz ederek, bu sefer bir sub-tree icerisinde aradigimiz node'lardan kac tanesinin olduguna bakmak. Ve bu bilgiyi recursive olarak bir yukaridaki level'a aktarmak. Ne zaman ki bu sayi (count) degeri 2 oldu, o zaman bu sub-tree'nin root node'u bizim aradigimiz LCA olacaktir.

def lowest_common_ancestor(tree, node0, node1):

# bir sub-tree'nin aradigimiz node'lardan kac tanesini barindirdigini ve

# ancestor degerini tutacak bir veritipine ihtiyac var

# tuple veya class da kullanilabilir ama namedtuple bayagi yaygin bu konuda

Status = collections.namedtuple("Status", ("num_target_count", "ancestor"))

# recursive olarak sub-tree'leri dolasacak fonskyinoumuz

def rec(root, node0, node1):

# egere root None ise, direk 0 donduruyoruz

# elbette ki ancestor da None oluyor

if not root:

return Status(0, None)

# sol sub-tree'ye bakalim

left_status = rec(root.left, node0, node1)

# eger solda zaten 2 sayisina ulasti isek

# LCA'yi bulduk demektir

if left_status.num_target_count == 2:

return left_status

# ayni sekilde sag sub-tree'yi kontrol ediyoruz

right_status = rec(root.right, node0, node1)

if right_status.num_target_count == 2:

return right_status

# bu noktada iki taraftan da aradigimiz

# 2 node'a ulasamadik. ama belki birisi bir tarafta

# digeri diger tarafta olabilir.

# ayrica rootun kendisi de aradigimiz node'lardan birisi olabilir

# bunu da toplama isleminde ensonda hesaba katiyoruz.

num_target_count = left_status.num_target_count + \

right_status.num_target_count + \

(node0, node1).count(root)

# eger bu toplama isleminden sonra 2 sayisina ulasabildiysek,

# ancestor root olacaktir.

return Status(num_target_count, root if num_target_count == 2 else None)

# recursion'u baslatiyoruz

return rec(tree, node0, node1).ancestor

DFS yine n kere donuyor ancak her bir dfs maliyeti O(1). Bu durumda toplamda O(n) time compl. ile onceki cozumu ilerletmis oluyoruz. Esktra space olarak sadece call stack'ten gelen O(h) oldugu gorulmekte.

4. Compute the LCA When Nodes Have Parent Pointers

Yukaridaki problemi, treenode'lari parent field'ina sahip olsa idi nasil cozebilirdik? Verilen fonskyion signature'u su sekilde: lca(node0, node1), yani root verilmiyor.

Cozum

Root verilmemesi daha guzel cunku diger turlu kafa karsitirici olabilir. Node'larin parent'leri bilindigine gore, iki node'u da itere ederek root'a kadar gidecegiz. Bunu yaparken de, iki node'un da gectigi yolu kaydedecek ve surekli birbirleri icerisinde ayni degere sahip olup olmadiklarini kontrol edecegiz. Cunku LCA'ya denk geldigimizde bu iki node'un path'i kesismis demektir.

def lca_with_parent(node0, node1):

# pathleri list icerisinde tutuyoruz

p0 = [node0]

p1 = [node1]

while True:

# eger p0'in son elemani p1 icerisinde var ise

if p0[-1] in p1:

return p0[-1]

if p1[-1] in p0:

return p1[-1]

# yukariya dogru itere etmeye devam

if p0[-1].parent:

p0.append(p0[-1].parent)

if p1[-1].parent:

p1.append(p1[-1].parent)

Olay bu kadar. Bakacak olursak, while loop icerisinde iki adet in kontrolu var ki, O(n) maliyete sahip. While dongusu de tree'nin yuksekligi kadar maksimum calisacagi icin toplamda O(nh) gibi bir maliyete sahip oluyoruz. Ekstra space de yine path tuttutugumuz icin O(h) seklinde olmaktadir.

Burada bize ek maliyet getiren yer in kontrolu. Bundan kurtulabilir miyiz? Ilk etapta neden buna ihtiyacimiz var? Cunku verilen node'lar ayni seviyede olmayabilir. Bu durumda tum path history'si icerisinde arama yapmak durumunda kaliyoruz. Ama node'lar ayni level'da olsa idi, direk esitlik operatoru ile ayni olduklarini anlayabilirdik.

Ornegin node 7 ve node 6 ayni levelde olmadiklari icin, bu ikisini ayni anda itere etsek bile, surekli butun historyleri kontrol etmek zorunda kaliyoruz. Ayrica hangisi root'a daha yakin (yani depth degeri dusuk) onu da bilmedigimiz icin iki history'i birden kontrol etmek gerekiyor.

Bu acidan bakarsak, once depth degerlerini elde ettigimizi dusunelim. Bunu O(h) ile yapmak mumkun. Daha sonra hangisinin depth degeri daha yuksek ise, onu, depth degeri az olanin hizasina gelinceye kadar itere edebiliriz. Ornekte, 7'yi 1 kere itere edersek 6 hizasina geldigini gorebiliriz. (Cunku aralarindaki depth farki 1).

Ve bir kere ayni hizaya getirdikten sonra, ikisini ayni anda itetere edebiliri. 6 ve 2 ornegin 1 kere itere edildiginde ayni node'a (5) ulasiliyor, demek ki bu iki node icin LCA, 5 imis.

def lca_with_parent(node0, node1):

# once depth hesaplayan fonk.

def depth(node):

ret = 0

while node.parent:

node = node.parent

ret += 1

return ret

# iki node icin de depth hesaplayalim

d0 = depth(node0)

d1 = depth(node1)

# kolaylik olsun diye node0'i, depth'i kucun olan

# olacak sekilde ayarliyoruz.

# yani node0'in depthi buyuk ise, bunu node1 olarak

# degistirelim

if d0 > d1:

node0, node1 = node1, node0

# simdi depthi yuksek olani aradaki fark kadar

# itere ederek iki node'u ayni hizaya cekiyoruz

depth_diff = abs(d0 - d1)

while depth_diff:

d1 = d1.parent

depth_diff -= 1

# suan ikisi ayni hizaya geldi

while node0 != node1:

node0 = node0.parent

node1 = node1.parent

# burada node0 == node1 haline geldi

# iksiinden birisini dondurebiliriz

return node0

Tekrar bakacak olursak iki kere depth hesapliyoruz ki maliyeti O(h). Daha sonra depthi yuksek olani itere ediyoruz, aradaki fark en fazla h olabilir (node0 root, depth = 0 ve node1 de leaf node, depth = h). Bu durumda burasi da O(h) maliyete sahip. Daha sonra ikisini birden roota kadar itere ediyoruz. Eger bir onceki depth_diff zaten worst case ise, ikisi de root'ta oluyor ve son while dongusu O(1) calisiyor. Yani gozuken o ki, son iki dongu toplamda O(h) maliyete sahip. Sonuc olarak toplamda O(h) time compl. ve ekstra space gereksinimi ise O(1) olan cok daha iyi bir cozum elde etmis olduk.

5. Sum The Root-To-Leaf Paths In Binary Tree

Root'tan baslamak uzere, her bir node, bir binary digit (0 veya 1) tasiyacak sekilde bir binary tree var. Root'tan, herhangi bir leaf node'a gidene kadar olusan yol bir binary sayiyi temsil ediyor. Verilen binary tree'deki binary sayilarin toplamini hesaplayan bir algoritma tasarlayiniz.

Cozum

Yani her bir leaf node aslinda bir binary sayiyi temsil ediyor. Ilk akla gelen naive yontem, dfs ile tum leaf'lere giden path'leri hesaplamak, bunlari decimal'a cevirip toplamak.

def sum_root_to_leaf(tree):

# yine path hesaplayan dfs

def dfs(node, path):

if not node:

return []

# leaf node'a geldik

elif not node.left and not node.right:

return [path + [node.data]]

else:

return dfs(node.left, path + [node.data]) + \

dfs(node.right, path + [node.data])

# [1, 0, 0, 1] seklinde olan bir path'i decimal

# sayiya ceviriyoruz

def path_to_decimal(path):

ret = 0

for d in path:

ret = ret * 2 + d

return ret

paths = dfs(tree, [])

ret = 0

for path in paths:

ret += path_to_decimal(path)

return ret

Simdi dogrulari acik acik konusmak gerekirse (frankly speaking), dfs fonksiyonu cok maliyetli. Neden? Cunku array concat islemi var ki her seferinde yeni bir list olusturuyor, ve onceki listlerin hepsini kopyalamak zorunda. Bu da O(n)'e tekabul ediyor. Tree'deki her bir node icin dfs calisacagindan, O(n^2) maliyetine ulasiyoruz. Onun disinda geri kalan kisim lineer ama sonucta cozum O(n^2). Esktra space kullanimi da oldukca fazla. Her bir leaf node icin h uzunlugunda bir array tutuyoruz. Sonuc olarak, leaf node sayisina m dersek, worst case scenario icin 2^h adet leaf node olur. O(h 2^h) gibi bir maliyet bizi bekliyor.

Tum pathleri tek tek hesapliyoruz ancak, path'lerin root'a yakin kisimlari aslinda ayni. Root noktasinda tum pathler ayni gittikce ozellesiyor. Ama yine de, pathler arasindaki bu overlap'i, algoritmayi optimize etmek icin kullanabiliriz.

Yani toplama islemini giderken yapabiliriz. Her bir yeni node'a rastladigimizda, simdiye kadar olusturdugumuz toplam degerini 2 ile carpip o node'un degeri ile toplarsak, binary olarak o node'u sayinin sonuna eklemis oluyoruz.

def sum_root_to_leaf(tree):

# recursive olarak node'lari dolasip

# toplamlari hesaplayan dfs fonk.

def dfs(node, smm):

if not node:

return 0

# simdiye kadar olusan toplam degerine

# bu node'un degerini de ekliyoruz

path_sum = path_sum * 2 + node.data

# leaf node'a gelmis isek, path_sum degerini dondur

if not node.left and not node.right:

return path_sum

else:

# leaf node'da degil isek, yolumuza toplayarak devam ediyoruz

return dfs(node.left, path_sum) + dfs(node.right, path_sum)

return dfs(tree, 0)

Hem daha basit bir cozum hem de daha performansli. Bakacak olursak her bir dfs adiminda yapilan islem O(1). Yani toplamda O(n) ile tum toplam islemini halletmis olduk. Ekstra space kullanimi da sadece dfs icin gerekli olan call stack, ki bu da O(h) olmaktadir.

6. Find A Root-To-Leaf Path With Specified Sum

Her bir node'u bir integer deger olan bir binary tree veriliyor. Root'tan leaf'e kadar olan node degerleri toplami da o leaf icin root-to-leaf-path degeri olarak kabul ediliyor. Verilen bir integer degeri icin, herhangi bir leaf node'un bu degerde root-to-leaf degerine sahip olup olmadigini kontrol eden bir algoritma tasarlayiniz.

Cozum

Naive cozum ile yine tum leaf node'lar icin path toplam degerlerini hesaplayip, aranan degerde olan var mi diye kontrol edebiliriz. Bunun yerine, yine onceki problemde yaptigimiz gibi, tree'yi traverse ederken toplamlari da hesaplayip, leaf node'a denk geldigimizde, toplam degerinin aranan deger olup olmadigina bakabiliriz. Bu sayede yine O(n) bir cozum elde etmis oluruz.

Bir noktaya dikkat etmek gerekiyor. Sonucta boyle bir toplam root-to-path deger var mi yok mu diye bakmak gerekiyor. Yani biz bir boolean dondurecegiz. Ama dfs icerisinde sadece toplam dondurursek, bu bilgiyi ust node'lara aktaramayiz. Yine daha once yaptigimiz gibi, her bir sub-tree'den yukariya dogru birden fazla bilgi tasimak icin bir namedtuple kullanacagiz.

from collections import namedtuple

def has_path_sum(tree, target_sum):

Status = namedtuple("Status", ("path_sum", "has_target"))

def dfs(node, smm):

if not node:

return Status(0, False)

# mevcut noda'a gelene kadar olan node degerleri toplami

path_sum = smm + node.data

# lead node'a gelmis isek

if not node.left and not node.right:

return Status(path_sum, target_sum == path_sum)

else:

# leaf node degil ise sol ve sag taraflari kontrol ediyoruz

left_sum = dfs(node.left, path_sum)

if left_sum.has_target:

return left_sum

right_sum = dfs(node.right, path_sum)

if right_sum.has_target:

return right_sum

# henuz target_sum'a ulasamadik

return Status(left_sum + right_sum, False)

return dfs(tree, 0).has_target

En kotu durumda her bir node'u bir kere ziyaret ediyoruz ve de her bir dfs adimi constant time maliyetinde. Bu durumda toplamda O(n) time compl. var ve ekstra memory gereksinimi de sadece recursiondan mutevellit call stack'ten gelen O(h).

Neler Ogrendik?

Bintree balanced mi?
Bagzi problemlerde, sub-tree'lerden yukariya birden fazla bilgi pass edilmedi gerekebilir. Ornegin balanced olup olmadigini anlamak icin tum sub-treeleri kontrol etmek ve herbir sub-tree icin height ile balanced olup olmadigi bilgisi yukariya pass etmek gerekiyor. Bunu bir tuple veya class ile yapabiliriz.

Ornek: class Subtree(is_balanced, height)
LCA problemi de yine ayni sekide yukariya data pass edilerek cozulebiliyor.
Root-to-path-sum gibi degerler, tum pathleri hesaplamak yerine running-sum ile hesaplanirsa daha performansli olur. Yani her bir node ziyaret edildiginde, o node'a kadar olan sum uzerine mevcut node degeri eklenerek, ilerlenilebilir. Leaf node'a gelindiginde ise, toplam sum degeri elde edilmis olunur.

Arkadaslar, binary tree demek programcilign kendisi demek. Zaten her bir bilgisayar programi bir tree degil midir? Bir sonraki postta binary tree problemlerine devam edecegiz.

Gorusmek uzere, Ciao!

lombak şehidi