Binary TreesTreeNode · DFS preorder / inorder / postorder · BFS level order · bottom-up & top-down
الـ tree هي basically linked list كل node فيها ليها اتنين next بدل واحد. والـ key insight اللي هتحل بيه أغلب المسائل: حلّها للـ root بس، من الإجابات اللي راجعة من الشمال ومن اليمين.
هتطلع من الفصل ده وإنت عارف
- كل الـ vocabulary: root و parent و child و leaf و edge و depth و height و level و subtree، وتشاور عليها في رسمة.
- تكتب
class TreeNode، وتقرا الـ array اللي LeetCode بيكتب بيها الـ tree (بالـnull)، وتبنيها بإيدك عشان تجرّب حلولك locally. - تفكّر في أي مسألة tree بسؤال واحد: «لو الولاد رجّعولي إجاباتهم، أحسب إجابتي إزاي؟».
- تكتب preorder و inorder و postorder (recursive و بـ stack)، و level order بـ queue، وتعرف إمتى تستخدم أنهي واحد.
- تحل 8 مسائل مشهورة، كل واحدة بتضيف فكرة جديدة: Max Depth و Invert و Same Tree و Symmetric و Path Sum و Diameter و LCA و Right Side View.
ليه Trees؟ ويعني إيه tree أصلًا
في الفصل اللي فات اتعلمت إن الدالة تنادي نفسها على مشكلة أصغر، وإنك trust the function من غير ما تدخل جواها. الفصل ده هو المكان اللي الكلام ده بيفرق فيه بجد.
كل الداتا اللي شفناها لحد دلوقتي كانت في خط واحد: array، string، linked list. بس داتا كتير مش خط، دي تفريعات: الفولدرات على جهازك، الـ DOM بتاع أي صفحة HTML (الـ body جواه div جواه button)، الـ JSON المتداخل اللي بيرجع من الـ API، الـ org chart في الشركة. كل دول trees.
فاكر الـ linked list؟ كل node فيها value و pointer واحد اسمه next. الـ binary tree نفس الفكرة بالظبط، بس كل node فيها اتنين pointers: left و right. ده الفرق كله.
الـ vocabulary اللي هتسمعه في كل مسألة
امشي مع الرسمة، كل step كلمة واحدة:
| الكلمة | معناها | في الرسمة |
|---|---|---|
| root | الـ node اللي فوق خالص، مالهاش parent. هي الـ entry point الوحيد اللي المسألة بتديهولك | 8 |
| parent / child | node والـ node اللي تحتها على طول | 3 هي parent لـ 1 و 6 |
| leaf | node مالهاش children، الاتنين null | 1 و 4 و 7 و 14 |
| edge | الخط بين parent و child. أي tree فيها n nodes فيها n - 1 edge | 8 nodes، 7 edges |
| depth | عدد الـ edges من الـ root لحد الـ node. الـ root عمقها 0 | depth الـ 4 = 3 |
| level | كل الـ nodes اللي ليها نفس الـ depth | level 1 = {3, 10} |
| height | عدد الـ edges في أطول طريق نازل من الـ node لـ leaf. الـ leaf ارتفاعها 0 | height الـ 8 = 3 |
| subtree | أي node + كل اللي تحتها، وهي نفسها tree كاملة | 3 و 1 و 6 و 4 و 7 |
null بيرجّع 0، والـ leaf بترجّع 1، يعني بنعدّ nodes.
أهم كلمة في الجدول هي subtree: كل tree = root + subtree شمال + subtree يمين، والـ subtrees دي trees هي كمان، لحد ما نوصل لـ tree فاضية (null). التعريف نفسه recursive، وعشان كده الـ recursion هي اللغة الطبيعية للـ trees.
طب إزاي تعرف من كلام المسألة إنها tree، وأنهي نوع حل هتحتاج؟
إزاي تعرفه من المسألة
الجزء السهل: الـ input نفسه غالبًا root من نوع TreeNode. الجزء المهم إنك تعرف أنهي shape من الحلول هتستخدم.
لو قال Binary Search Tree، فيه ترتيب بيوفّر عليك اللف، وده الفصل الجاي. لو فيه cycles أو node ليها أكتر من parent، دي graph. ولو «أكبر k عناصر»، غالبًا heap.
| الـ shape | السؤال اللي بتسأله | بيتكتب إزاي | أمثلة هنا |
|---|---|---|---|
| Bottom-up DFS | إجابة الـ node جاية من إجابات ولادها؟ | نادي الشمال واليمين، واجمع اللي رجع | Max Depth، Invert، Same Tree، Symmetric |
| Top-down DFS | الـ node محتاجة info من اللي فوقها؟ | ابعت الـ info كـ parameter | Path Sum |
| DFS + global best | الإجابة path بيلف عند node في النص؟ | رجّع height، وحدّث متغير برا | Diameter |
| BFS level by level | حاجة لكل level؟ أقرب حاجة للـ root؟ | queue + levelSize | Level Order، Right Side View |
flowchart TD
A["Tree problem"] --> B{"Need something for each level?"}
B -- yes --> BFS["BFS: queue + levelSize"]
B -- no --> C{"Answer at a node comes from its children?"}
C -- yes --> D{"Answer is a path that bends at some node?"}
D -- yes --> G["Return height, update a global best"]
D -- no --> U["Bottom-up DFS: return a value"]
C -- no --> T["Top-down DFS: pass info down as a parameter"]
اسأل الأسئلة دي بالترتيب. أغلب الـ easy بتقع في Bottom-up DFS.
قبل أي shape من دول، محتاج تعرف الـ node نفسها شكلها إيه في JavaScript.
الـ TreeNode في JavaScript
LeetCode بيكتبلك الـ class دي في comment فوق الحل. احفظها، لأنك هتحتاجها عشان تجرّب حلولك على جهازك، وممكن تتطلب منك في الانترفيو.
- ليه الـ default
nullمشundefined؟ عشان كل الحلول بتسألnode.left === null. لو سبتهاundefinedالشرط هيطلع false على leaf، وهتقرا.valمنundefinedوتضرب error. - دول references مش نسخ. الـ node مش شايلة ولادها جواها، هي بس عارفة عنوانهم، زي
nextفي الـ linked list. - المتغير
rootهو الحاجة الوحيدة اللي في إيدك. أي node تانية بتوصلها بإنك تبدأ من هنا وتنزل. root.left.right: روح شمال، وعلّق على يمينها. لوroot.leftكانتnullهتضربTypeError: Cannot set properties of null، وده الـ error اللي هتشوفه كتير لو نسيت الـ null check.- نفس الـ tree from the bottom up: لازم الولاد يتعملوا الأول عشان يتبعتوا للـ constructor. مفيد في الـ tests الصغيرة.
في الـ memory: الـ array صندوق واحد متصل، فـ nums[5] بـ O(1). الـ tree لأ: كل node object لوحده، و left و right مجرد عناوين. يعني مفيش index، ولازم تبدأ من الـ root وتنزل. وأي node (حتى الـ root نفسه) ممكن تبقى null، فأي كود بيقرا node.val لازم يتأكد الأول إنها مش null.
طب LeetCode بيكتب الـ tree في الـ examples كـ array. الـ array دي بتتقري إزاي؟
LeetCode بيكتب الـ tree إزاي: الـ array بالـ null
هتلاقي الـ input مكتوب كده: root = [1,2,3,null,4,5,6,null,null,7]. ده مش array بيوصل للدالة، دي طريقة كتابة: الـ judge بيبني الـ tree ويبعتلك الـ root بس. القواعد:
- بتتقري level by level، وكل level من الشمال لليمين.
- كل node موجودة بنكتب قيمتها، وكل child مش موجود بنكتب مكانه
null. - الـ
nullمالهاش ولاد، فمش بنكتب حاجة مكان ولادها. ده أهم سطر هنا. - الـ
nulls اللي في آخر الـ array بتتشال.
يعني في المثال: الـ 1 root، ولادها 2 و 3. ولاد الـ 2: null و 4. ولاد الـ 3: 5 و 6. ولاد الـ 4: null و null. وبعدين الـ 7 شمال الـ 5، والباقي nulls اتشالت.
2i + 1 هنا
الـ 2i + 1 و 2i + 2 دول format الـ heap، وفيه كل الأماكن محجوزة. هنا الـ null اللي عند index 3 ما حجزش أماكن لولاده، فلو حسبت بـ 2i + 1 هتعمل الـ 7 ابن الـ 4. وهي ابن الـ 5.
على LeetCode مش هتكتب الدالة دي، بس عشان تجرّب حلك locally في Node، لازم تبني الـ tree من الـ array. وهي تمرين ممتاز على الـ queue:
- tree فاضية (
[]) = root بـnull. - ليه queue؟ الـ array مكتوبة level by level، فالآباء بياخدوا ولادهم بنفس ترتيب ما اتعملوا. First in, first out، يعني queue.
- ليه
headمشshift()؟ الـshift()بيزق كل العناصر خطوة، فهو O(n)، و n مرة يبقى O(n²). بالـheadالـ dequeue بقى O(1). queue[head++]: اقرا اللي عندheadوبعدين زوّده. ده الـ dequeue.- لو مش
null، نعمل الـ child وندخّله الـ queue عشان ياخد ولاده بعدين. ولوnullمش بندخّل حاجة، وده بالظبط معنى «الـ null مالهاش ولاد». - بنزوّد
iفي الحالتين، لأن الـnullخدت مكان في الـ array. - ليه
i < arr.lengthهنا بس؟ الـ array ممكن تخلص بعد الـ left child على طول. من غيرهarr[i]هتبقىundefined، وundefined !== nullبتطلع true، فهتعمل node قيمتهاundefinedمن غير أي error.
الـ nodes المنقّطة مستنية في الـ queue، والصفرا هي الـ parent اللي بناخدله ولاده:
TreeNode و buildTree، وجرّب أي حل كده: console.log(maxDepth(buildTree([3,9,20,null,null,15,7]))). الـ debugging locally أسرع بكتير من إنك تفضل تدوس Run.
دلوقتي معاك tree حقيقية. إزاي تحسب عليها أي حاجة من غير ما تتوه في التفريعات؟
الفكرة الكبيرة: حلّها للـ root من إجابات الولاد
عايز مجموع كل القيم في الـ tree. لو فكّرت فيها كـ loop هتتوه: أمشي فين الأول؟ وأرجع للـ parent إزاي؟ بس بصّلها كده:
- مجموع الـ tree = قيمة الـ root + مجموع الـ subtree الشمال + مجموع الـ subtree اليمين.
- والـ subtree الشمال نفسها tree، فمجموعها بنفس القاعدة.
- لحد ما نوصل لـ tree فاضية (
null) مجموعها 0. ده الـ base case.
ده بالظبط الـ trust the function: لما تكتب treeSum(node.left) ما تدخلش جواها في دماغك. افترض إنها رجّعت مجموع الـ subtree الشمال كلها، وركّز على الـ node اللي قدامك. شغلتك كلها تلات أسئلة:
- لو الـ node بـ
null، أرجّع إيه؟ ده الـ base case. للمجموع: 0. - هطلب إيه من الشمال واليمين؟ نفس السؤال، على tree أصغر.
- أجمّع إجاباتهم مع الـ node إزاي؟ للمجموع:
node.val + left + right.
- الدالة بترجّع مجموع الـ tree اللي بتبدأ من هنا. لما تناديها بالـ root الأصلي، يبقى ده مجموع الـ tree كلها.
- أهم سطر. من غيره، أول ما توصل لـ leaf وتنادي على
leaf.left، هتقراnull.leftوتضربTypeError. وليه 0؟ عشان 0 مش بيغيّر المجموع. - «ثق»: كل نداء بيرجّع مجموع subtree كاملة. واليمين مش هيبدأ غير لما الشمال كله يخلص، وده معنى Depth-First.
- الحساب بيحصل بعد ما الولاد يرجعوا، فالإجابات بتطلع on the way back up. ده اسمه bottom-up.
الرقم تحت كل node هو اللي رجّعته لأبوها، والـ call stack بيوريك مين مستني مين:
نفس الـ skeleton بيحل مسائل كتير. اللي بيتغيّر بس إجابة السؤال الأول والتالت:
| المطلوب | null بيرجّع | الـ node بترجّع |
|---|---|---|
| مجموع القيم | 0 | node.val + L + R |
| عدد الـ nodes | 0 | 1 + L + R |
| عدد الـ levels (max depth) | 0 | 1 + Math.max(L, R) |
| أكبر قيمة | -Infinity | Math.max(node.val, L, R) |
لاحظ أكبر قيمة: الـ null بيرجّع -Infinity مش 0، عشان لو كل القيم سالبة الـ 0 هيكسب غلط. القاعدة: الـ base case لازم يبقى قيمة neutral ما تأثرش على الحساب.
الـ treeSum زارت كل node مرة واحدة بترتيب معيّن. طب لو عايز تطلّع الـ nodes نفسها في list، بأنهي ترتيب؟
DFS: preorder و inorder و postorder
الـ traversal يعني تزور كل node مرة واحدة. الـ DFS (Depth-First Search): انزل لآخر الفرع الشمال، وبعدين ارجع خطوة وجرّب اليمين، زي ما بتدوّر على فايل في فولدرات متداخلة. والـ recursion بتعمل ده by default، لأن كل نداء بيستنى اللي تحته يخلص.
التلات أنواع بيلفّوا على الـ nodes بنفس الترتيب بالظبط. الفرق الوحيد إمتى بتكتب الـ node بالنسبة لولادها:
| النوع | الترتيب | على [4,2,7,1,3,6,9] | use case |
|---|---|---|---|
| preorder | node، شمال، يمين | 4 2 1 3 7 6 9 | نسخ الـ tree أو serialize، الأب قبل ولاده |
| inorder | شمال، node، يمين | 1 2 3 4 6 7 9 | في الـ BST بيطلّع القيم sorted |
| postorder | شمال، يمين، node | 1 3 2 6 9 7 4 | الأب محتاج إجابات ولاده الأول: height، delete |
الاسم بيقولك مكان الـ node: pre = قبل الولاد، in = بينهم، post = بعدهم. والشمال دايمًا قبل اليمين.
Preorder: الـ node الأول
- ليه
outبراvisit؟ عشان كل النداءات تكتب في نفس الـ array. ده pattern «collect into an outer array» من الـ helpers. visitهي الـ helper اللي بتعمل الـ recursion، ومش بترجّع حاجة. شغلتها تكتب فيout.- الـ base case. ليه مش بنتشيك
node.left !== nullقبل النداء؟ ممكن، بس هتكرر الشرط وتحتاج check للـ root كمان. check واحد في أول الدالة بيغطي كل ده. - preorder: نكتب الـ node قبل أي حاجة تحتها، وبعدين الشمال كله، وبعدين اليمين كله.
- ولو الـ root نفسه
null؟ السطر 4 بيعمل early return وoutبتفضل[]. الـ empty tree متغطية for free.
الـ nodes المنقّطة لسه في الـ call stack مستنية، والخضرا اتكتبت في out:
Inorder: الـ node في النص
- الفرق كله هنا: قبل ما نكتب الـ node، ننزل الشمال كله. فأول حاجة تتكتب هي أقصى node على الشمال، مش الـ root.
- الـ node بتتكتب بعد ما الشمال يخلص، فالـ root (4) بييجي في النص.
- في الـ BST كل اللي شمال أصغر وكل اللي يمين أكبر، فالترتيب ده بيطلّع القيم sorted. ده هيبقى سلاحك في الـ BST.
Postorder: الـ node في الآخر
- الولاد الاتنين الأول، شمال وبعدين يمين.
- الـ node بتتكتب آخر حاجة، فالـ root هو آخر رقم في
out. - خد بالك: الـ
treeSumكانت postorder من غير ما نقول: الولاد الأول، وبعدين الحساب على الـ node. أي حل bottom-up هو postorder.
out.push بس هو اللي بيتنقل. Complexity: كل node مرة، يعني O(n) time. والـ memory هي أطول call stack، يعني O(h): O(log n) لو الـ tree balanced، و O(n) في الـ worst case لو مايلة كلها في خط.
الـ O(h) دي مش ببلاش: لو الـ tree عميقة جدًا الـ call stack هيتملي. طب نكتبها من غير recursion إزاي؟
DFS من غير recursion: stack بإيدك
سببين يخلّوك تكتبها iterative:
- الـ call stack ليه limit. في JS الـ recursion بتقع بعد حوالي 10 آلاف نداء متداخل بـ
RangeError: Maximum call stack size exceeded. جرّبتmaxDepthعلى tree مايلة: 10,000 node وقعت في Node 24، و 5,000 عدّت. شوف الجزء ده في الـ recursion. - Follow-up مشهور في الانترفيو: «اكتبها iterative».
الفكرة: الـ recursion كانت بتستخدم الـ call stack عشان تفتكر «أنا راجع لمين». إحنا هنعمل نفس الحاجة بـ stack عادي.
Preorder بـ stack
- هنا الـ check لازم، لأننا هنقرا
node.valمن غير check جوه الـ loop. - ناخد اللي فوق ونكتبه على طول. ده preorder.
- ليه اليمين الأول؟ الـ stack: last in, first out. عايزين الشمال يطلع الأول، فلازم يدخل آخر. لو عكستهم هتطلع node، يمين، شمال.
Inorder بـ stack
أصعب شوية: الـ node ما بتتكتبش أول ما توصلها. لازم تفتكرها، تنزل الشمال كله، وترجعلها. والـ stack هو اللي بيفتكر.
- ليه
||؟ نكمّل لو لسه فيه subtree جديدة (cur) أو nodes مستنية في الـ stack. لو كتبتstack.length > 0بس، الـ loop مش هتدخل أصلًا لأن الـ stack فاضي في الأول. - ننزل شمال لآخره، وكل node نعدّي عليها نحطها في الـ stack. ده اللي
visit(node.left)كانت بتعمله. - مفيش شمال تاني، فاللي فوق الـ stack هو أقصى node على الشمال لسه ما اتكتبتش.
- الدور على الـ subtree اليمين بتاعتها. لو
null، اللفة الجاية هتعمل pop للأب، وده «الرجوع» بتاع الـ recursion.
return out.reverse();. مقلوب «node، يمين، شمال» هو «شمال، يمين، node».
الـ DFS بينزل لتحت الأول. طب لو المسألة عايزة الـ tree level by level؟
BFS: level by level بـ queue
الـ BFS (Breadth-First Search) عكس الـ DFS: بيزور الـ level كله الأول، وبعدين اللي تحته. زي الميّة لما تنتشر في دواير حوالين الحجر.
رجّع قيم الـ tree level by level: كل level في array لوحدها، من الشمال لليمين.
- empty tree: نرجّع
[]مش[[]]. ومن غيره هنحطnullفي الـ queue ونضرب error. - نفس الـ
headtrick بتاعbuildTree: الـ queue الحقيقي هوqueue[head..]، و «مش فاضي» بقتhead < queue.length. - أهم سطر في الـ BFS. في اللحظة دي الـ queue فيه level واحد كامل بس. بنعمل freeze لعدده قبل الـ loop، لأن جوه الـ loop هنضيف ولاد والـ queue هيكبر. لو حطيت
queue.length - headفي شرط الـ for، هتاخد ولاد الـ level الجاي معاك. <مش<=: عايزينlevelSizeلفة بالظبط، من 0 لـlevelSize - 1.- الولاد يقفوا في آخر الـ queue، الشمال قبل اليمين، والـ
nullما بيدخلش. - الـ level خلص، نحطه في الإجابة. لو عايزها من تحت لفوق (LeetCode 107)،
res.reverse()في الآخر.
| DFS (recursion / stack) | BFS (queue) | |
|---|---|---|
| الترتيب | ينزل لآخر الفرع الأول | level by level |
| Time | O(n) | O(n) |
| Memory | O(h): طول أعمق طريق | O(w): أعرض level، لحد حوالي n/2 |
| استخدمه لما | الإجابة جاية من الولاد، أو path من الـ root لـ leaf | حاجة لكل level، أو أقرب حاجة للـ root |
كده معاك كل الأدوات: bottom-up و traversals و BFS. يلا نطبّقها على مسائل حقيقية، ونبدأ بأسهلها.
مثال محلول 1: Maximum Depth (بالـ DFS وبالـ BFS)
رجّع عدد الـ nodes في أطول طريق نازل من الـ root لأبعد leaf، يعني عدد الـ levels.
- التلات أسئلة:
null= 0 levels. أطلب من الولاد عمقهم. لو الشمال 2 واليمين 3، أنا عندي level زيادة فوق الأعمق:1 + max(2, 3). - ليه max مش جمع؟ الطريق بينزل في فرع واحد بس، ما ينفعش ينزل شمال ويمين مع بعض.
- حل تاني: «عدد الـ levels» دي كلمة BFS. نمشي level by level ونعدّ.
- ليه 0 مش 1؟
nullيعني مفيش node أصلًا. وبكده الـ leaf بتطلع1 + max(0, 0) = 1لوحدها، من غير special case. - trust the function: كل نداء بيرجّع عمق subtree كاملة.
- الـ
1دي الـ node نفسها، والـmaxعشان الطريق بيكمّل في الفرع الأعمق بس.
لاحظ الـ 3: رجّعت 2 مع إن الشمال بتاعها فاضي، لأن max(0, 1) = 1:
نفس المسألة بالـ BFS
depth = 0لأننا لسه ما خلّصناش ولا level.- نفس skeleton الـ level order، بس مش محتاجين نحفظ القيم.
depth++برا الـ for، مرة لكل level. لو حطيته جوه هيعدّ nodes مش levels.
Edge cases: [] → 0 (الـ base case على الـ root نفسه)، [1] → 1، و [1,null,2,null,3,null,4] → 4 (مايلة يمين: الـ worst case للـ DFS memory).
Complexity: الاتنين O(n) time. الـ DFS بياخد O(h) في الـ call stack، والـ BFS بياخد O(w) في الـ queue.
هنا كنا بنقرا الـ tree بس. طب لو عايزين نعدّلها نفسها؟
مثال محلول 2: Invert Binary Tree
اقلب الـ tree كأنها صورتها في المراية: في كل node، الشمال يروح اليمين واليمين يروح الشمال. رجّع الـ root.
الجديد هنا إن الدالة بتعدّل الـ tree in-place، وبترجّع node مش رقم.
- المراية بتقلب كل level: لو بدّلت ولاد الـ root بس، الـ 1 والـ 3 هيفضلوا بنفس ترتيبهم تحت الـ 2.
- التلات أسئلة:
null؟ مفيش حاجة تتقلب، رجّعnull. اطلب من الولاد «اقلبوا نفسكم». بعد ما يرجعوا، فاضل إيه؟ بدّل مكانهم. - احفظ قبل ما تكتب: لو كتبت
root.left = ...الأول، هتضيّع الـ reference القديم. نفس فكرة الـ swap بمتغير مؤقت.
- بنرجّع
nullلأن الأب هيحط اللي راجع مكان child، وnull= «مفيش child». - الـ subtrees بترجع مقلوبة خلاص، ومحفوظة في
leftوright، فمش هنضيّع حاجة لما نكتب فيroot.left. - الـ swap. كل subtree بتتنقل كاملة باللي تحتها.
- ليه نرجّع
root؟ الأب محتاج حاجة يحطها مكان الـ child، والمسألة عايزة الـ root. مفيش nodes جديدة، كله in-place.
Complexity: O(n) time، و O(h) memory. وممكن تعمل الـ swap الأول وبعدين تقلب الولاد (preorder)، النتيجة واحدة طالما كل node بتتبدّل مرة واحدة بس.
لحد دلوقتي الدالة بتمشي على tree واحدة. طب لو عايزين نقارن اتنين trees ببعض؟
مثال محلول 3: Same Tree
عندك root لـ tree اسمه p و root لـ tree تانية اسمه q. هل الاتنين متطابقين: نفس الشكل ونفس القيم في نفس الأماكن؟
الجديد هنا إن الدالة بتمشي على اتنين nodes مع بعض، واحدة من كل tree في نفس المكان.
- فكرة غلط: قارن الـ preorder بتاعهم.
[1,2]و[1,null,2]الاتنين preorder بتاعهم[1, 2]، مع إن شكلهم مختلف. الـ traversal بيضيّع الـ shape. - الـ recursive definition: متطابقين لو الـ roots واحد، و الشمال زي الشمال، و اليمين زي اليمين.
- تلات base cases بالترتيب: الاتنين
null(متطابقين). واحد بسnull(الشكل مختلف). القيم مختلفة.
- الاتنين فاضيين في نفس المكان = تطابق. دي الحالة اللي بتحصل عند ولاد أي leaf.
- ليه الترتيب مهم؟ الـ
||هنا معناه «واحد على الأقل». ولأن السطر اللي قبله شال حالة «الاتنين»، يبقى هنا «واحد بس». لو بدّلت السطرين، حالة الاتنينnullهترجّع false غلط. - دلوقتي متأكدين إن الاتنين موجودين، فقراية
.valsafe. كل سطر بيحمي اللي بعده. - الـ
&&بتعمل short-circuit: لو الشمال طلع مختلف، اليمين مش هيتقارن أصلًا.
الشجرتين جنب بعض. الدايرة الرمادية مش جزء من المسألة، هي بس ماسكاهم في رسمة واحدة:
Complexity: O(n) time (n = عدد nodes الأصغر فيهم) و O(h) memory.
طب لو الاتنين nodes اللي بنقارنهم جوه نفس الـ tree، بس في مكانين معكوسين؟
مثال محلول 4: Symmetric Tree
هل الـ tree صورة نفسها في المراية حوالين خط نازل من الـ root في النص؟
الجديد هنا إن الدالة اللي المسألة بتديهالك (isSymmetric(root)) مش كفاية، فبنعمل helper بـ parameters مختلفة، ونقارن crossed.
- إيه اللي لازم يتساوى؟ الشمال بتاع الـ root لازم يبقى مراية لليمين، مش نسخة منه.
- محتاجين اتنين pointers في ناحيتين مختلفتين، زي Same Tree. بس في المراية: الخارجي مع الخارجي (
a.leftمعb.right)، والداخلي مع الداخلي (a.rightمعb.left).
- الـ root على خط المراية ومالوش زوج. الشغل الحقيقي في helper بياخد اتنين nodes.
- نفس الـ base cases بتاعة Same Tree، بنفس الترتيب ولنفس الأسباب.
- ده السطر الوحيد اللي اتغيّر. لو كتبت
a.leftمعb.leftهتبقى بتسأل «هل الشمال نسخة من اليمين؟»، وده Same Tree مش مراية.
Edge cases: [] و [1] الاتنين true. [1,2,2,2,null,2] false: كل القيم 2، والـ shape هو اللي بيفرق. Complexity: O(n) time و O(h) memory.
في كل اللي فات، المعلومة كانت بتطلع من تحت لفوق. طب لو الـ node محتاجة تعرف حاجة عن اللي فوقها؟
مثال محلول 5: Path Sum (top-down)
هل فيه طريق من الـ root لحد leaf مجموع قيمه بيساوي targetSum؟ القيم ممكن تبقى سالبة.
الجديد هنا إن المعلومة نازلة من فوق لتحت كـ parameter، وده اسمه top-down.
- الـ node محتاجة تعرف «اتجمع كام لحد هنا»، ودي معلومة عند اللي فوقها.
- trick: بدل ما نبعت المجموع ونقارنه، نبعت الباقي: كل node تطرح قيمتها. لو وصلنا leaf والباقي 0، لقينا طريق. وكده نستخدم الدالة الأصلية من غير helper.
- بنتشيك عند الـ leaf (الشمال واليمين
null)، مش عند الـnull. هتشوف ليه في[1,2]. - early stop لما المجموع يعدّي الـ target؟ لأ. القيم ممكن تبقى سالبة، والـ -3 في المثال هي اللي خلّت الطريق ينفع.
- ليه false مش
targetSum === 0؟nullمش leaf. لو رجّعتtargetSum === 0، الـ tree[1,2]مع target 1 هتطلع true غلط: اليمين الفاضي بتاع الـ 1 هيقول «الباقي 0»، والـ 1 مش leaf أصلًا. - الـ
remainingهو اللي باقي الطريق (من تحت) لازم يجمّعه. - الـ leaf هي المكان الوحيد اللي الطريق ينفع يخلص فيه.
===لأن المطلوب يساوي بالظبط. - الـ
||بتعمل short-circuit: لو الشمال لقى طريق، اليمين مش هيتسأل. ولو child واحدnull، هيرجّع false من سطر 2 والتاني هو اللي يقرر.
الرقم تحت كل node هو remaining عندها. الـ target هو 18:
Edge cases: [], 0 → false (مفيش طريق أصلًا). [1], 1 → true (الـ root نفسه leaf). [-2,null,-3], -5 → true. Complexity: O(n) time و O(h) memory.
طب لو الطريق المطلوب مش نازل من الـ root، وممكن يلف عند أي node في النص؟
مثال محلول 6: Diameter of Binary Tree
رجّع طول أطول طريق بين أي اتنين nodes، بعدد الـ edges. الطريق ممكن ما يعدّيش على الـ root.
الجديد هنا إن الدالة بترجّع حاجة وبتسجّل حاجة تانية: بترجّع للأب الـ height، وبتحدّث متغير برا بالإجابة.
- شكل أي طريق: بيطلع لحد node معيّنة (أعلى نقطة)، وبعدين ينزل من الناحية التانية. يعني كل طريق ليه node بيلف عندها.
- أطول طريق بيلف عند X =
height(X.left) + height(X.right)edges، لو الـ height بيعدّ nodes (null = 0). - Brute force: لكل node احسب الـ heights من الأول: O(n²) في tree مايلة.
- الـ key insight: الـ
heightنفسها بتعدّي على كل node، ومعاهاleftوrightفي نفس اللحظة. نسجّلleft + rightفيbestوإحنا معدّيين. one pass، O(n).
bestبرا الـ helper عشان كل النداءات تشوفه. بيبدأ 0 لأن tree بـ node واحدة طولها 0 edges.- الـ helper هو
maxDepthبالظبط، postorder. - بنسجّل، مش بنرجّع.
left + right= الطريق اللي بيلف هنا بالـ edges. ومش+ 1، لأن ده كان هيبقى عدد الـ nodes. - بنرجّع، مش بنسجّل. الأب محتاج طريق مستقيم نازل يكمّل عليه. الطريق اللافف ما ينفعش يتوصّل بالأب، كده هيعدّي على الـ node مرتين.
- بنتجاهل اللي
height(root)رجّعه، والإجابة فيbest.
الرقم تحت كل node هو الـ height اللي رجّعته. لاحظ إن الـ best اتحدد عند الـ 2، مش عند الـ root:
Edge cases: [1,2] → 1 (بـ left + right + 1 هتطلع 2 غلط). [1,2,3,4,5] → 3، وهنا الطريق بيعدّي على الـ root. وفي المثال اللي فوق لو حسبت عند الـ root بس هتطلع 3 بدل 4.
Complexity: one pass، O(n) time و O(h) memory. ونفس الـ pattern بيحل Binary Tree Maximum Path Sum (124).
لحد دلوقتي الدالة بترجّع رقم أو boolean. طب لو محتاجة ترجّع node لقيتها؟
مثال محلول 7: Lowest Common Ancestor
عندك tree واتنين nodes p و q موجودين فيها أكيد. رجّع أوطى node ليها الاتنين تحتها. والـ node بتتحسب ancestor لنفسها.
الجديد هنا إن كل نداء بيرجّع «اللي لقيته» (node أو null)، والقرار بيتاخد من إجابة الناحيتين مع بعض.
- بالتشبيه: أقرب جد مشترك لابن عمين هو الجد اللي واحد منهم في فرعه الشمال والتاني في فرعه اليمين.
- السؤال لكل subtree: «لقيت جواك
pأوq؟ رجّعلي اللي لقيته، أوnull». - عند كل node: لو الناحيتين رجّعوا حاجة، أنا نقطة التفرّع، يعني أنا الإجابة. لو ناحية واحدة بس، أطلّع اللي رجع لفوق زي ما هو.
- ولو الـ node نفسها
p؟ early return من غير ما ندوّر تحتها. لوqتحتها فهي الإجابة أصلًا، ولوqفي حتة تانية، ancestor فوق هيلاقي حاجة من الناحيتين.
root === pمشroot.val === p. الـpوqهنا nodes، فبنقارن الـ reference نفسه.- الاتنين مش
null: واحد في كل ناحية. الطريق بينهم لازم يعدّي عليّا، وأنا أوطى node بتعمل كده. - ناحية واحدة لقت حاجة (أو ولا ناحية). نطلّعها زي ما هي. ولو الإجابة الحقيقية اتلقت تحت، هتطلع كده لحد الـ root.
p = 4 و q = 9. الرقم تحت كل node هو اللي رجّعته، و - يعني null:
Edge cases: p = 2, q = 9 → 2 (سطر 3 بيرجّع الـ 2 من غير ما ينزل). p = 8, q = 9 → 5 (إخوات). p = 1 → 1 (الـ root نفسه). Complexity: O(n) time و O(h) memory. الحل ده بيعتمد إن الاتنين موجودين، والمسألة بتضمن ده.
آخر مثال بيرجّعنا للـ BFS، بس المرة دي مش عايزين كل الـ level، عايزين node واحدة منه.
مثال محلول 8: Binary Tree Right Side View
تخيل إنك واقف على يمين الـ tree. رجّع القيم اللي هتشوفها، من فوق لتحت.
الجديد هنا إن الـ BFS بقى بيختار node معيّنة من كل level، باستخدام الـ index k جوه الـ level.
- الفخ: «امشي يمين على طول». في
[1,2]مفيش يمين، وإنت هتشوف الـ 2. وفي المثال الأول الـ 6 ابن شمال، ومحدش قدامها. - إنت بتشوف إيه؟ من كل level، آخر node من اليمين. يعني BFS بـ
levelSize، وناخدk === levelSize - 1.
- نفس الـ level order بالحرف. لو حافظ الـ BFS، المسألة دي سطر واحد جديد.
- ليه
levelSize - 1؟ الـkبيبدأ من 0، فآخر واحدة رقمهاlevelSize - 1. لو كتبتk === levelSizeالشرط عمره ما هيتحقق والإجابة هتطلع فاضية. - بندخّل الشمال كمان. ممكن يكون هو اللي باين في level تحت (زي الـ 6).
في الـ DFS، الـ depth نازل top-down، و res.length = عدد الـ levels اللي لقينا ليها node. لو depth === res.length يبقى أول مرة ننزل الـ level ده، ولأننا بنروح يمين الأول، أول واحدة هي اللي باينة. Complexity: الاتنين O(n) time، الـ BFS بـ O(w) memory والـ DFS بـ O(h).
كده حلّينا 8 مسائل. يلا نجمع الغلطات اللي بتوقّع الناس فيهم في مكان واحد.
غلطات مشهورة
أغلب الـ Wrong Answer والـ Runtime Error في الـ trees بييجوا من الغلطات دي، وكلها سطر واحد.
1. نسيت الـ base case
ولاد أي leaf null، فالنداء على null هيحصل أكيد. أول سطر في أي recursive function على tree: «لو null أعمل إيه».
2. كتبت فوق الـ pointer قبل ما تحفظه
السطر التاني بيقرا root.left بعد ما اتغيّر. احفظ الاتنين في const الأول، أو [root.left, root.right] = [root.right, root.left]; وبعدين اقلب الولاد.
3. اتشيكت على الـ null بدل الـ leaf
أي مسألة فيها «root-to-leaf» الـ check بيبقى على node.left === null && node.right === null. الـ null معناها «مفيش node»، مش «الطريق خلص».
4. رجّعت الإجابة بدل اللي الأب محتاجه
اسأل نفسك دايمًا: «الأب هيعمل إيه باللي راجعله؟». الأب بيكمّل عليه، فلازم يرجعله طريق مستقيم (height)، والإجابة تتسجّل برا.
دلوقتي اختبر نفسك: أسئلة سريعة، وتمرين تفكّر فيه قبل ما تفتح الحل.
اختبر نفسك
الـ array [1,null,2,3] بتمثّل tree. الـ 3 فين؟
- الـ right child بتاع الـ 1
- الـ left child بتاع الـ 1
- الـ left child بتاع الـ 2
- الـ right child بتاع الـ 2
ولاد الـ 1 هما null و 2. الـ null مالهاش ولاد، فأول node مستنية في الـ queue هي الـ 2، والـ 3 هي الشمال بتاعها. بـ 2i + 1 كانت هتطلع ابن الـ null، وده مستحيل.
إيه الـ inorder للـ tree [5,3,8,1,4]؟
- 5 3 1 4 8
- 1 3 4 5 8
- 1 4 3 8 5
- 5 3 8 1 4
شمال، node، يمين: الـ subtree 3 (1, 4) بتطلع 1 3 4، وبعدين 5، وبعدين 8. الأولى preorder، والتالتة postorder، والرابعة level order.
الـ DFS الـ recursive على tree فيها n node مايلة كلها في خط. الـ memory كام؟
- O(1)، مفيش arrays
- O(log n)
- O(n)
- O(n²)
كل نداء بيفضل في الـ call stack لحد ما اللي تحته يخلص، فهيبقى فيه n نداء متداخلين. الـ memory هي O(h)، والـ h هنا = n.
في Diameter، الـ helper height بترجّع إيه للأب؟
- الطريق اللافف عندها
left + right - الـ
bestلحد دلوقتي - الـ height بتاعها
1 + max(left, right)، والطريق اللافف بيتسجّل فيbestبس - عدد الـ nodes في الـ subtree
الأب بيكمّل على اللي راجعله، والطريق ما ينفعش يلف مرتين. فبيرجعله طريق مستقيم، والطريق اللافف يتسجّل برا.
hasPathSum([1,2], 1) بترجّع إيه في الحل الصح؟
- true، لأن الـ root قيمته 1
- false، لأن الـ 1 مش leaf، والطريق الوحيد 1 → 2 مجموعه 3
- error
- true، لأن اليمين بتاع الـ 1 فاضي
الطريق لازم يخلص عند leaf. الاختيار الرابع هو الغلطة رقم 3 بالظبط.
تمرين: فكّر قبل ما تفتح
رجّع عدد الـ nodes في أقصر طريق من الـ root لـ leaf. شكلها Max Depth بـ Math.min، صح؟ جرّب الفكرة على المثال التاني قبل ما تفتح.
تلميح 1
جرّب 1 + Math.min(left, right) على المثال التاني: شمال الـ 2 null فبيرجّع 0، فالإجابة هتطلع 1. بس الـ 2 مش leaf! الـ null مش طريق.
تلميح 2
لو child واحد بس null، كمّل في الناحية الموجودة بس. الـ min بيتاخد لما الاتنين موجودين. أو فكّر BFS: أول leaf تقابلها هي الأقرب، فتقف عندها على طول.
الحل
لو الاتنين null (leaf)، السطر 3 هيرجّع 1 + minDepth(null) = 1، صح. وبالـ BFS كمان تقدر: أول leaf تقابلها level by level هي الإجابة، فتعمل early return من غير ما تلف على كله. «أقصر» = BFS بيحبها، «أطول» = لازم تشوف كله.
لو الأسئلة دي عدّت معاك، روح على LeetCode بالترتيب اللي تحت.
اتمرن على LeetCode بالترتيب
كل مسألة بتضيف فكرة واحدة على اللي قبلها. قبل أي حل قول التلات أسئلة: «الـ null بيرجّع إيه؟ هطلب إيه من الولاد؟ أجمّع إزاي؟». ولو عدّيت 25 دقيقة، ارجع للمثال المحلول اللي شبهها.
- Maximum Depth of Binary Treeالمثال 1. اكتب الـ DFS والـ BFS من دماغك.
- Invert Binary Treeتعديل in-place. احفظ قبل ما تكتب فوق.
- Same Treeاتنين nodes مع بعض، و 3 base cases بترتيب.
- Symmetric TreeSame Tree بس crossed، وأول helper بـ parameters مختلفة.
- Subtree of Another Treerecursion بتنادي recursion: لكل node اسأل Same Tree.
- Binary Tree Inorder Traversalrecursive، وبعدين iterative بـ stack من غير ما تبص.
- Binary Tree Level Order Traversaltemplate الـ BFS بـ
levelSize. هتستخدمه في الـ graphs. - Binary Tree Right Side ViewBFS + سطر واحد. وجرّب نسخة الـ DFS.
- Minimum Depth of Binary Treeالتمرين اللي فوق: فخ الـ min مع الـ null.
- Path Sumأول top-down، والـ check عند الـ leaf.
- Diameter of Binary Treeرجّع height وسجّل الإجابة برا.
- Balanced Binary Treeنفس pattern الـ Diameter، وزيادة: رجّع
-1كـ «مش balanced» واعمل early exit. - Lowest Common Ancestor of a Binary Treeالمثال 7: رجّع «اللي لقيته»، والـ split هو الإجابة.
- Construct Binary Tree from Preorder and Inorderاختياري وأصعب: أول preorder هو الـ root، ومكانه في الـ inorder بيقسم الشمال من اليمين. hash map للمكان.
وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.
الخلاصة
null بيرجّع إيه، اطلب الإجابة من الشمال واليمين وثق فيها، واجمعها. ولو المطلوب حاجة لكل level، queue.
| السؤال | الإجابة |
|---|---|
| أول سطر في الدالة؟ | if (node === null) return ... دايمًا، بقيمة neutral: 0 للجمع، -Infinity للـ max. |
| null ولا leaf؟ | «root-to-leaf» = اتشيك على الـ leaf. الـ null مش آخر طريق. |
| DFS ولا BFS؟ | BFS لو «level» أو «أقرب». DFS لأي حاجة تانية تقريبًا. |
| pre ولا in ولا post؟ | post لو الأب محتاج ولاده. pre لو الولاد محتاجين الأب. in للـ BST. |
| edges ولا nodes؟ | اقرا المسألة: Max Depth بالـ nodes، Diameter بالـ edges. |
| Complexity؟ | O(n) time تقريبًا دايمًا. Memory: O(h) للـ DFS، O(w) للـ BFS. |
الفصل الجاي: Binary Search Tree هي binary tree بقاعدة زيادة: كل اللي شمال أي node أصغر منها وكل اللي يمينها أكبر. القاعدة دي بتخلّيك تختار شمال ولا يمين من غير ما تلف على كله، فالـ search بيبقى O(h) بدل O(n). وكل اللي هنا (الـ null check، trust the children، والـ inorder اللي بيطلّع sorted) هتستخدمه هناك على طول.