Binary Search TreeBST property · search · insert · delete · inorder · validate

الـ BST هي binary tree ماشية بقاعدة واحدة: كل اللي على شمال الـ node أصغر منها، وكل اللي على يمينها أكبر منها. القاعدة دي بتخلّي كل مقارنة تشيل جزء كامل من الـ tree مرة واحدة، زي الـ binary search بالظبط، بس من غير ما تزق عناصر كل ما تضيف أو تمسح.

قبله: Binary Trees و Binary Search بيمهّد لـ: Heap و Priority Queue

هتطلع من الفصل ده وإنت عارف

  • القاعدة بتاعة الـ BST بالظبط، وليه إنك تقارن الـ node بأولادها المباشرين بس مش كفاية.
  • تعمل search و insert في O(h)، وتمسح node في حالاتها التلاتة، وتعرف ليه بناخد الـ inorder successor بالذات.
  • ليه الـ inorder traversal بتاعة أي BST بتطلع مترتبة، وإزاي تستغل ده في Kth Smallest و Validate.
  • الفرق بين tree متوازنة (h حوالي log n) و tree مايلة (h = n)، وليه ده بيقلب الـ complexity.
  • تحل Search و Insert و Validate BST و Kth Smallest و LCA و Sorted Array to BST، وتشرح كل سطر في انترفيو.

ليه BST؟

في الفصل اللي فات الـ tree كانت مجرد شكل: أي قيمة في أي node. فلو عايز تدوّر على رقم، لازم تلف عليها كلها O(n). دلوقتي هنضيف قاعدة ترتيب واحدة، وهتخلّي الـ search يمشي في طريق واحد بس من فوق لتحت.

تخيّل سيستم فيه أرقام بتدخل وتخرج طول الوقت (مثلًا أسعار أوردرات)، وعايز تسأل: الرقم ده موجود؟ إيه أصغر رقم؟ إيه أقرب رقم أصغر من أو يساوي 50؟ طلّعلي كل الأرقام مترتبة. تعالى نشوف الأدوات اللي تعرفها:

الأداةتدوّرتضيف / تمسحأقرب رقم أصغر / الترتيبالمشكلة
array عاديةO(n)O(1) / O(n)O(n) / O(n log n)لازم تلف على كله في كل سؤال
sorted arrayO(log n)O(n)O(log n) / جاهزكل insert بيزق نص الـ array لقدّام
Hash SetO(1)O(1)مش بيعرف الترتيب خالصممتاز في "موجود ولا لأ" بس
BSTO(h)O(h)O(h) / O(n)كويسة لو الـ h صغيرة (هنشوف ده)

الـ BST بتجمع الحلو من الاتنين: سريعة في الـ search زي الـ sorted array، وسريعة في الـ insert والـ delete لأنها مش محتاجة تزق حاجة، كل اللي بيتغيّر pointer أو اتنين. الـ h هنا هو الـ height بتاع الـ tree، وهنفهم بعد شوية إنه ممكن يبقى حوالي log n وممكن يبقى n.

تذكير سريع بالـ tree (لو ناسيها)
  • node: خانة فيها قيمة val واتنين pointers: left و right. أي واحد فيهم ممكن يبقى null لو مفيش حاجة هناك.
  • root: أول node فوق خالص. الـ tree كلها بتدخل عليها من الـ root.
  • parent و child: الـ node هي parent للـ nodes اللي تحتها مباشرة، وهما children بتوعها.
  • leaf: node مالهاش أولاد خالص، الاتنين null.
  • subtree: أي node ومعاها كل اللي تحتها. لما نقول "الـ left subtree بتاعة الـ 8" نقصد ابنها الشمال وكل اللي تحته لآخره.
  • ancestor: أي node فوقك على الطريق من الـ root ليك: أبوك، وجدّك، وجد جدّك.
  • height (h): عدد المستويات من الـ root لأبعد leaf. tree فيها node واحدة الـ h بتاعها 1. ده نفس الـ maxDepth اللي في فصل الـ trees.
تشبيه فاكر لعبة "أنا فكرت في رقم، قول أكبر ولا أصغر"؟ أذكى طريقة إنك تسأل عن رقم في النص، ولما يقولك "أصغر" ترمي كل الأرقام اللي فوق مرة واحدة. الـ BST هي اللعبة دي متخزّنة: كل node سؤال "أكبر ولا أصغر؟"، والإجابة بتقولك تنزل يمين ولا شمال، والناحية التانية كلها بتترمي من غير ما تبص عليها.

بص على الـ search جوه BST فيها 8 أرقام. تحت الـ tree نفس الأرقام في array مترتبة، عشان تشوف إن كل خطوة بتشيل جزء كامل زي الـ binary search:

4 مقارنات بس. والأهم: كل مرة نزلنا فيها ناحية، الناحية التانية كلها اترمت بمقارنة واحدة. لو الـ tree متوازنة وفيها مليون رقم، الطريق من الـ root لأي leaf حوالي 20 node بس، فالـ search بيبقى حوالي 20 مقارنة.

طب إزاي تعرف إن المسألة BST، وأنهي خاصية فيها هتستغلها؟ ده الجزء الجاي.

إزاي تعرفه من المسألة

أغلب مسائل الـ BST بتقولك صراحة "binary search tree". الشطارة مش إنك تعرف إنها BST، الشطارة إنك تعرف أنهي خاصية هتستغلها:

لما تشوف: binary search treekth smallestvalidateinorder successor closest valuefloor / ceilingrange sumsorted array to tree lowest common ancestor of BSTinsert / delete node
ومش هو غالبًا لو: binary tree (من غير search)kth largest in a streamبس "موجود ولا لأ"

لو المسألة قالت "binary tree" بس، يبقى مفيش ترتيب، ومينفعش تنزل ناحية واحدة. ساعتها ارجع لـ DFS و BFS العاديين من فصل الـ trees. ولو المطلوب أكبر k عناصر من داتا بتيجي على طول، ده heap. ولو كل اللي محتاجه "موجود ولا لأ" من غير ترتيب، Set أسهل وأسرع.

النوعبتستغل إيهالـ complexityمسائل
امشي في طريق واحدالقاعدة: كل مقارنة بتقولك يمين ولا شمالO(h)Search، Insert، LCA، Floor / Closest
الـ inorder مترتبشمال ثم node ثم يمين = تصاعديO(n) أو O(h + k)Kth Smallest، Validate، Min Difference
حدود من فوقكل node ليها range مسموح (low, high)O(n)Validate BST
بناء وتعديلالنص يبقى root، والـ successor مكان المحذوفO(n) / O(h)Sorted Array to BST، Delete Node
flowchart TD
  A["Problem says BST?"] --> B{"Need one value or one spot?"}
  B -- yes --> W["Walk one path: go left or right, O(h)"]
  B -- no --> C{"Need values in sorted order, or the kth?"}
  C -- yes --> I["Inorder traversal: left, node, right"]
  C -- no --> D{"Check the tree is a real BST?"}
  D -- yes --> V["Pass low and high bounds down"]
  D -- no --> T["Plain tree DFS / BFS"]
  

اسأل نفسك الأسئلة دي بالترتيب ده.

كل الأنواع دي قايمة على قاعدة واحدة. يلا نفهمها بالظبط، لأن فيها فخ مشهور.

القاعدة بالظبط: كل الشمال أصغر، وكل اليمين أكبر

التعريف الصح للـ BST: لكل node في الـ tree، كل القيم في الـ left subtree بتاعتها أصغر منها، وكل القيم في الـ right subtree أكبر منها. وده لازم يتحقق عند كل node، مش عند الـ root بس.

خلي بالك من كلمة كل. القاعدة مش "الابن الشمال أصغر من أبوه والابن اليمين أكبر من أبوه". دي حاجة أضعف بكتير، ومعظم الناس بتقع فيها أول مرة. الـ animation دي فيها tree كل أب فيها مع أولاده المباشرين تمام، ومع كده هي مش BST:

شفت اللي حصل؟ الـ 12 موجودة في الـ tree، والـ search ما لقاهاش. السبب إن الـ search بيثق في القاعدة: لما قارن 12 بالـ 10 قال "أكبر، يبقى يمين أكيد"، ورمى الشمال كله. فلو القاعدة مكسورة في أي حتة، كل العمليات اللي بتعتمد عليها بتطلّع نتايج غلط من غير أي error.

ليه القاعدة لازم تبقى على الـ subtree كلها لأن الـ search بيرمي subtree كاملة بمقارنة واحدة. عشان الرمي ده يبقى آمن، لازم نكون متأكدين إن كل اللي في الـ subtree دي في الناحية الغلط. لو القاعدة على الأولاد المباشرين بس، الضمان ده بيضيع.

طب والأرقام المكررة؟

في أغلب مسائل LeetCode الأرقام في الـ BST مش بتتكرر، والقاعدة strict: left < node < right. لو مسألة سمحت بالتكرار، لازم تختار ناحية واحدة للمتساوي (مثلًا اليمين: left < node <= right)، وتلتزم بيها في الـ insert والـ search والـ validate. لو الـ insert حط المتساوي يمين والـ search دوّر عليه شمال، مش هتلاقيه أبدًا.

طالما القاعدة صح، الـ search بيبقى أسهل حاجة في الفصل. يلا نكتبه.

مثال محلول 2: Insert into a BST

Insert into a Binary Search Tree

mediumLeetCode 701

ضيف قيمة جديدة val للـ BST بحيث تفضل BST، ورجّع الـ root. القيمة مضمون إنها مش موجودة قبل كده. أي شكل صح مقبول.

Input: root = [8,3,10,1,6,null,14], val = 4 Output: [8,3,10,1,6,null,14,null,null,4] (4 becomes the left child of 6)

نفكّر فيها مع بعض

  1. الجديد هنا: مش بس بنمشي، بنعدّل الـ tree. والسؤال المهم: فين المكان الصح؟ لو هندوّر على 4 بعد ما نضيفها، الـ search هيمشي طريق معيّن. يبقى لازم نحطها في آخر الطريق ده بالظبط، وإلا الـ search مش هيلاقيها.
  2. الفكرة: نعمل search عادي على val. هو مش موجود، فالـ search هيقع في null في الآخر. المكان الفاضي ده هو مكان الـ node الجديدة. يعني الـ node الجديدة دايمًا بتبقى leaf.
  3. ليه القاعدة مش هتتكسر؟ عند كل ancestor على الطريق، إحنا نزلنا الناحية الصح بالمقارنة. فالـ 4 أصغر من كل node نزلنا شمالها، وأكبر من كل node نزلنا يمينها. وده بالظبط شرط القاعدة.
  4. التفصيلة: مش هينفع نقع في null وبعدين نعلّق، لأن ساعتها هنكون نسينا مين الأب. فنبص على الابن قبل ما ننزل: لو فاضي نعلّق فيه على طول، لو مش فاضي ننزل.
  5. الحالات الطرفية: tree فاضية: الـ node الجديدة هي الـ root. الإضافة على أقصى الشمال أو أقصى اليمين.
  1. بنعمل الـ node الجديدة من الأول. لسه مش متعلّقة في أي حتة.
  2. لو الـ tree فاضية، الـ node الجديدة هي الـ tree كلها. من غير السطر ده، السطر الجاي هيخلّي node = null، وأول node.val هيضرب error.
  3. نبدأ من الـ root ونمشي زي الـ search.
  4. while (true) معناها "لف لحد ما حد يعمل break". ده آمن هنا لأن كل لفة بتنزّل مستوى، والـ tree ليها آخر، فأكيد هنلاقي مكان فاضي ونعمل break.
  5. ليه < مش <=؟ المسألة بتضمن إن val مش موجودة، فالمساواة مش هتحصل. لو مسألة تانية سمحت بالتكرار، المتساوي هيروح اليمين (الـ else)، ولازم الـ search يمشي بنفس الاتفاق.
  6. بنبص على الابن الشمال قبل ما ننزل له. لو null، يبقى ده المكان اللي الـ search كان هيقع فيه، فنعلّق الجديدة ونخرج.
  7. مش فاضي، فننزل مستوى ونكمّل.
  8. نفس الكلام بالظبط ناحية اليمين، لما val أكبر.
  9. بنرجّع الـ root القديم. الإضافة عمرها ما بتغيّر الـ root، إلا في حالة الـ tree الفاضية اللي رجّعناها في السطر 3.

هنضيف 4 وبعدين 7 على tree فيها 6 أرقام. لاحظ إن الطريق هو هو طريق الـ search:

لو بصيت للنتيجة، هي نفس الـ tree اللي في أول الفصل. أي BST ممكن تتبني كده: تبدأ فاضية، وتضيف القيم واحدة واحدة.

والـ recursive version مشهورة جدًا، وفيها حركة لازم تفهمها كويس لأنها هتتكرر في الـ delete:

ليه root.left = insertIntoBST(...) ومش مجرد insertIntoBST(root.left, val)؟ لما نوصل لمكان فاضي، الـ call بترجّع node جديدة، بس محدش ماسكها. الـ assignment هو اللي بيعلّقها في أبوها. ولو الابن مش فاضي، الـ call بترجّع نفس الابن، فالـ assignment بيكتب نفس القيمة تاني ومبيغيّرش حاجة. القاعدة: كل call بترجّع الـ root بتاع الـ subtree بتاعها بعد التعديل، والأب بيربطه.

التعقيد: O(h) وقت. الـ iterative O(1) memory، والـ recursive O(h).

الإضافة دايمًا leaf، فسهلة. طب المسح؟ الـ node ممكن تبقى في النص وتحتها ناس.

الـ delete: تلات حالات

المسح أصعب من الإضافة، لأن الـ node اللي هتمسحها ممكن تكون في نص الـ tree وتحتها ناس. لما تشيلها، لازم حد ياخد مكانها والقاعدة تفضل ماشية. أول خطوة سهلة: نلاقيها بنفس طريق الـ search. بعد كده عندنا تلات حالات حسب عدد أولادها:

الحالةنعمل إيهليه ده صح
1. leaf (مالهاش أولاد)نشيلها: أبوها يشاور على nullمفيش حد تحتها يتأثر
2. ابن واحدالابن ياخد مكانها: أبوها يشاور على ابنهاالابن وكل اللي تحته كانوا في نفس الناحية من الجد، فهيفضلوا صح
3. ابنينننسخ فيها قيمة الـ inorder successor (أصغر قيمة في يمينها)، وبعدين نمسح الـ successor من تحتالـ successor أكبر من كل الشمال، وأصغر من كل اللي فاضل في اليمين
تشبيه مدير قسم ساب الشغل. لو مالوش حد تحته، المكتب بيتقفل وخلاص. لو تحته شخص واحد، الشخص ده بيترقّى مكانه بفريقه كله. لو تحته فريقين، بنجيب من الفريق اليمين أقل واحد فيهم، ونقعّده على الكرسي، لأنه الوحيد اللي "أكبر" من كل الفريق الشمال و"أصغر" من باقي الفريق اليمين، فالترتيب ما يتلخبطش.
  1. زي الـ insert الـ recursive بالظبط: الدالة بترجّع الـ root الجديد للـ subtree بعد المسح، والأب بيربطه. ده بيحل مشكلة "مين أبو الـ node اللي بنمسحها" من غير ما نمسك pointer للأب.
  2. وقعنا من الـ tree من غير ما نلاقي key. يبقى مش موجود، ونرجّع null عشان الأب يفضل زي ما هو (كان بيشاور على null أصلًا).
  3. نفس قرار الـ search. المسح هيحصل جوه الشمال، والشمال ممكن يرجع بـ root جديد، فبنكتبه في root.left. لو نسيت الـ assignment، المسح مش هيوصل للـ tree.
  4. لقينا الـ node. من هنا الحالات التلاتة.
  5. بيغطّي حالتين مع بعض. لو مالهاش شمال: يا مالهاش يمين كمان (leaf، فبنرجّع null والأب بيشيلها)، يا ليها يمين بس (فبنرجّع اليمين ياخد مكانها). في الحالتين return root.right هو الصح.
  6. ليها شمال بس، فالشمال ياخد مكانها. لو وصلنا هنا يبقى root.left مش null أكيد، لأن السطر اللي فوق كان هيرجع.
  7. ابنين: الـ inorder successor هو أصغر قيمة أكبر من الـ node، يعني يمين مرة وبعدين شمال لآخره. بنقف لما succ.left === null، مش لما succ نفسه يبقى null.
  8. بدل ما نحرّك nodes ونلخبط pointers، بننسخ القيمة بس. دلوقتي القيمة دي موجودة مرتين: هنا وتحت.
  9. نمسح النسخة اللي تحت من الـ right subtree. ليه ده مش هيلف لا نهائي؟ لأن الـ successor مالوش ابن شمال (إحنا وقفنا عنده عشان كده)، فمسحه هيبقى حالة 1 أو 2، سطر 8 بالظبط.
  10. لو ما مسحناش الـ node دي نفسها، الـ root بتاع الـ subtree ما اتغيّرش، فبنرجّعه زي ما هو.

حالة 1: نمسح leaf

نمسح الـ 7. لاحظ الـ call stack على الشمال: كل call مستنية اللي تحتها ترجع عشان تربط النتيجة.

حالة 2: نمسح node ليها ابن واحد

نمسح الـ 10، وليها ابن يمين بس (14):

حالة 3: نمسح node ليها ابنين

نمسح الـ 3، وليها الـ 1 شمال والـ 6 يمين. هنا لازم الـ successor:

ينفع الـ predecessor بدل الـ successor؟ أيوه. الـ inorder predecessor هو أكبر قيمة في الشمال (يمين لآخره جوه الـ left subtree)، وهو كمان أكبر من كل الشمال الباقي وأصغر من كل اليمين. الاتنين صح، بس اختار واحد واكتبه من غير تفكير. الـ successor هو المشهور.

التعقيد: بننزل مرة لحد الـ node، ومرة كمان لحد الـ successor، وكله على نفس الطريق تقريبًا، فالوقت O(h). والـ memory O(h) للـ recursion. المسألة دي هي LeetCode 450، وموجودة في قايمة التمرين.

كل اللي فات بيمشي في طريق واحد. فيه خاصية تانية للـ BST بتبان لما تلف عليها كلها: الترتيب.

الـ inorder بتاع أي BST بيطلع مترتب

الـ inorder traversal معناها: لكل node، اطبع كل الشمال الأول، وبعدين الـ node نفسها، وبعدين كل اليمين. في فصل الـ trees كانت مجرد ترتيب من تلاتة. هنا ليها معنى مهم جدًا: في BST، الـ inorder بيطلّع القيم تصاعدي.

ليه؟ خد أي node. كل اللي في الشمال أصغر منها، وبيتطبع قبلها. كل اللي في اليمين أكبر منها، وبيتطبع بعدها. فالـ node دي واقفة في مكانها الصح بالظبط بالنسبة لكل الـ subtree بتاعتها. ونفس الكلام بيحصل جوه الشمال وجوه اليمين (نفس الدالة بتتنادى عليهم)، فالترتيب كله صح من أوله لآخره.

  1. بنبعت array out بنملاها. ممكن ترجّع array جديدة من كل call، بس ده بيعمل نسخ كتير، والـ array المشتركة أسرع.
  2. الـ base case. من غيره الدالة هتنادي null.left وتضرب error. كل leaf ليها اتنين null، فالسطر ده بيتنفّذ كتير جدًا (n + 1 مرة بالظبط).
  3. الترتيب ده هو اللي بيعمل الفرق. لو كتبت السطر 4 قبل السطر 3 هتطلع preorder، ولو بعد السطر 5 هتطلع postorder، والاتنين مش مترتبين.
  4. لحظة ما نوصل هنا، كل اللي أصغر من node جوه الـ subtree دي اتطبع خلاص.
  5. وبعدين الأكبر. الـ complexity: كل node بتتطبع مرة واحدة، فالوقت O(n)، والـ memory O(h) للـ call stack.

الحقيقة دي هتستخدمها في نص مسائل الـ BST: Kth Smallest (العنصر رقم k في الـ inorder)، Validate (الـ inorder لازم يبقى تصاعدي بشكل strict)، Minimum Difference (أقرب رقمين لازم يبقوا جنب بعض في الـ inorder)، و Two Sum على BST.

كل العمليات اللي فاتت O(h). طب الـ h ده قد إيه بالظبط؟

متوازنة ولا مايلة: الـ h بيفرق قد إيه

كل العمليات اللي فاتت O(h). طب الـ h ده قد إيه؟ بيعتمد على ترتيب الإضافة. نفس الأرقام من 1 لـ 7، مرة نضيفهم بترتيب "النص الأول"، ومرة بالترتيب العادي:

نفس الأرقام بالظبط، بس التانية بقت linked list مايلة، وده الـ worst case. كل insert بيلف على كل اللي قبله، والـ search على 7 بيعمل 7 مقارنات. الـ BST هنا ما بقاش ليها أي ميزة على array عادية.

nh لو متوازنة (حوالي log₂ n)h لو مايلة (= n)
737
1,000101,000
1,000,000201,000,000
قول O(h) مش O(log n) في الانترفيو لما تقول complexity عملية على BST، قول O(h)، وبعدين وضّح: "O(log n) لو متوازنة، و O(n) في أسوأ حالة لو مايلة". لو قلت O(log n) على طول، الـ interviewer ممكن يسألك "وليه متأكد إنها متوازنة؟".

في الـ production فيه BSTs بتوازن نفسها أوتوماتيك بعد كل insert (اسمها AVL و Red-Black)، فالـ h بيفضل O(log n) دايمًا. الـ std::set و std::map في C++ والـ TreeMap في Java جوّاهم Red-Black tree. JS معندهاش حاجة زي دي built-in. ومش مطلوب منك تكتب AVL في انترفيو، بس لازم تعرف إنها موجودة وليه.

كده معاك كل الأساسيات. يلا نلمّها في قالبين هتستخدمهم في كل المسائل.

القالبين اللي هتستخدمهم في كل مسائل الـ BST

القالب الأول: امشي في طريق واحد، وافتكر أحسن مرشّح

كتير من المسائل مش عايزة القيمة نفسها، عايزة "أقرب حاجة ليها". مثلًا الـ floor: أكبر قيمة في الـ tree أصغر من أو تساوي x. نفس طريق الـ search، بس كل ما نعدّي على قيمة تنفع، نحفظها كمرشّح ونكمّل ندوّر على أحسن منها:

  1. best = null معناها "لسه ما لقيناش أي قيمة تنفع". لو كل القيم أكبر من x، هترجع null زي ما هي. ما تبدأش بـ 0: الصفر ممكن يبقى قيمة حقيقية، وممكن تكون الأرقام كلها سالبة.
  2. هنا الشرط node !== null بس، لأننا مش بنقف لما نلاقي حاجة. بنفضل ننزل لحد ما نقع، عشان ممكن يكون فيه مرشّح أحسن تحت.
  3. لو لقينا x نفسها، مفيش حاجة أكبر منها وأصغر من أو تساوي x. نرجّع على طول.
  4. الـ node أصغر من x فهي candidate. ممكن يكون فيه أكبر منها ولسه <= x، وده لازم في يمينها. ومش محتاجين Math.max: كل candidate جديد جاي من يمين اللي قبله، فهو أكبر.
  5. الـ node أكبر من x، فهي ما تنفعش، وكل اليمين بتاعها أكبر منها فما ينفعش برضه. ننزل شمال.
  6. وقعنا من الـ tree. آخر مرشّح حفظناه هو الإجابة.

الـ ceiling (أصغر قيمة أكبر من أو تساوي x) هو نفس الكود بالعكس. ومسألة Closest Binary Search Tree Value (LeetCode 270، بس premium) هي نفس الفكرة: امشي في طريق واحد، وافتكر الأقرب.

القالب التاني: inorder بـ stack (عشان تقدر تقف بدري)

الـ inorder الـ recursive سهل، بس صعب توقفه في النص. النسخة دي بتعمل نفس الحاجة بـ stack إنت ماسكه بإيدك، فتقدر تطلع منها في أي لحظة. هتشوفها شغالة في Kth Smallest تحت.

  1. الـ stack هنا بيعمل شغل الـ call stack بتاع الـ recursion: بيفتكر الـ nodes اللي نزلنا شمالها ولسه ما طبعناهاش.
  2. ليه الشرطين بـ ||؟ فيه وقت يبقى node = null (خلّصنا ناحية) بس الـ stack لسه فيه ناس مستنية. وفيه وقت يبقى الـ stack فاضي بس node لسه فيه subtree يمين ما اتلفّش. الـ loop تخلص بس لما الاتنين يخلصوا.
  3. ننزل شمال لآخر حاجة، وكل node نعدّي عليها نحطها في الـ stack. ده نفس السطر 3 في الـ recursive: "خلّص الشمال الأول".
  4. اللي فوق الـ stack هي أصغر قيمة لسه ما اتطبعتش، لأن كل اللي في شمالها اتطبع أو مش موجود. نطبعها.
  5. وبعدين نروح يمينها. الـ while اللي جوه هتنزل شمال الـ subtree دي في اللفة الجاية. لو اليمين null، الـ while اللي جوه مش هتدخل، وهنطلّع اللي بعدها من الـ stack.

أول تطبيق: القالب الأول، بس بـ target اتنين بدل واحد.

مثال محلول 3: Lowest Common Ancestor of a BST

الأول: يعني إيه lowest common ancestor (LCA)؟ خد اتنين nodes، p و q. الـ common ancestors هما الـ nodes اللي فوق الاتنين مع بعض (الـ root دايمًا واحد منهم). الـ lowest هو أوطى واحد فيهم، يعني الأقرب ليهم. والـ node تتحسب ancestor لنفسها، فلو p جد q، الإجابة p.

تشبيه شجرة العيلة: إنت وابن عمك، أقرب جد مشترك ليكم هو جدّك (أبو أبوك وأبو أبوه). جد جدّك مشترك برضه، بس مش الأقرب. وإنت وأبوك، أقرب "جد مشترك" هو أبوك نفسه.

Lowest Common Ancestor of a Binary Search Tree

mediumLeetCode 235

عندك BST واتنين nodes موجودين فيها p و q. رجّع الـ LCA بتاعهم.

Input: root = [8,3,10,1,6,null,14,null,null,4,7], p = 4, q = 7 Output: 6 Input: same tree, p = 3, q = 4 Output: 3 (3 is an ancestor of 4, and of itself)

نفكّر فيها مع بعض

  1. الجديد هنا: القالب الأول بالظبط، بس بنمشي ورا قيمتين مع بعض بدل واحدة، ونقف لما يفترقوا.
  2. في binary tree عادية المسألة دي محتاجة DFS على الـ tree كلها (LeetCode 236)، O(n). بس هنا عندنا BST، فأكيد فيه حاجة أسهل.
  3. الفكرة: ابدأ من الـ root. لو p و q الاتنين أصغر منها، يبقى الاتنين في الشمال، والـ LCA في الشمال برضه. لو الاتنين أكبر، يبقى في اليمين.
  4. وإمتى نقف؟ أول node الاتنين يفترقوا عندها: واحد في الشمال وواحد في اليمين. دي آخر node مشتركة بينهم، لأن أي نزلة بعدها هتسيب واحد فيهم. أو أول node تكون هي نفسها p أو q.
  5. الحالتين دول شرط واحد: "مش الاتنين أصغر، ومش الاتنين أكبر". ده بيغطّي الافتراق، ويغطّي إن واحد فيهم يساوي الـ node.
  1. p و q هنا nodes مش أرقام، فبنقارن بـ p.val. لو قارنت p < node.val هتقارن object برقم، والنتيجة false دايمًا من غير error.
  2. نفس شكل الـ search: طريق واحد من فوق لتحت.
  3. الاتنين أصغر strictly، فالاتنين في الشمال. الـ node دي common ancestor، بس فيه واحد أوطى منها في الشمال.
  4. نفس الكلام يمين.
  5. هنا الافتراق: يا واحد أصغر وواحد أكبر، يا واحد فيهم هو الـ node. وعشان كده فوق < مش <=: لو p هي الـ node ونزلت، هتضيّع الإجابة.
  6. المسألة بتضمن إن الاتنين موجودين، فمش هنوصل هنا.

التعقيد: طريق واحد، فالوقت O(h) والـ memory O(1). قارنه بـ O(n) في الـ binary tree العادية: الـ BST وفّرت علينا نلف على كله.

طب لو المطلوب مش node معيّنة، المطلوب رقم k في الترتيب؟ هنا ييجي القالب التاني.

مثال محلول 4: Kth Smallest Element in a BST

Kth Smallest Element in a BST

mediumLeetCode 230

رجّع القيمة رقم k لو رتّبت قيم الـ BST تصاعدي. الـ k بيبدأ من 1، يعني k = 1 هو أصغر قيمة.

Input: root = [8,3,10,1,6,null,14,null,null,4,7], k = 3 Output: 4 (sorted: 1, 3, 4, 6, 7, 8, 10, 14)

نفكّر فيها مع بعض

  1. الجديد هنا: مش طريق واحد، ده traversal كامل بالترتيب، والمطلوب نقف في النص (early stop).
  2. الربط: "رقم k في الترتيب" + "BST" = الـ inorder. الـ inorder بيطلّع القيم مترتبة، فالإجابة هي العنصر رقم k اللي يطلع منه.
  3. أول حل: اعمل inorder كامل في array، ورجّع out[k - 1]. ليه k - 1؟ عشان الـ k بيبدأ من 1 والـ array من 0. ده O(n) وقت و O(n) memory.
  4. نقدر أحسن؟ لو k = 1، ليه نلف على مليون node؟ أول ما نطلّع العنصر رقم k نقف. هنا بييجي القالب التاني (الـ inorder بـ stack)، لأن الوقوف في النص فيه مجرد return.
  5. الخطة: بدل الـ out، عدّاد. كل ما نطلّع node من الـ stack ننقّص k. لما يوصل صفر، دي الإجابة.
  6. الحالات الطرفية: k = 1 (أقصى الشمال)، k = n (أقصى اليمين، هنلف على كله)، tree مايلة.
  1. نفس بداية القالب التاني بالظبط.
  2. ننزل شمال لآخره ونحط كل node في الـ stack. في الـ tree بتاعتنا، أول مرة هنحط 8 و 3 و 1.
  3. اللي فوق الـ stack هو العنصر الجاي في الترتيب.
  4. بنستخدم k نفسه كعدّاد تنازلي بدل ما نعمل count ونقارنه بـ k. أول عنصر بيخلّي k يبقى k - 1، والعنصر رقم k بيخلّيه صفر بالظبط.
  5. ليه k === 0 بعد الـ k-- مش قبله؟ لو قارنت قبل ما تنقّص، هتقف عند العنصر رقم k + 1. جرّب بإيدك على k = 1: أول عنصر يطلع، k يبقى 0، فنرجّعه. صح.
  6. لسه ما وصلناش، نكمّل في يمين الـ node دي.
  7. مش هيحصل في LeetCode لأن الـ k مضمون صح، بس الدالة لازم ترجّع حاجة في كل الطرق.

التعقيد: بننزل h مستوى في الأول، وبعدين بنطلّع k عناصر، فالوقت O(h + k) مش O(n). والـ memory O(h) للـ stack. لو k صغير والـ tree متوازنة، ده أسرع بكتير من إنك تلف على كله.

سؤال المتابعة المشهور "لو الـ tree بتتعدّل كتير (insert و delete) وإنت بتسأل عن الـ kth كل شوية؟" الإجابة: خزّن في كل node عدد الـ nodes في الـ subtree بتاعتها. ساعتها عند أي node تعرف كام واحد في شمالها، فتعرف تنزل يمين ولا شمال من غير ما تلف، والسؤال يبقى O(h). مش لازم تكتب الكود، بس قول الفكرة.

لحد دلوقتي كنا بنثق إن الـ tree BST. طب لو حد اداك tree وسألك: هي BST ولا لأ؟

مثال محلول 5: Validate Binary Search Tree

Validate Binary Search Tree

mediumLeetCode 98

عندك binary tree. هل هي BST صح؟ يعني لكل node، كل اللي في شمالها أصغر منها strictly، وكل اللي في يمينها أكبر منها strictly.

Input: root = [10,5,15,2,12] Output: false (12 sits in 10's left subtree, but 12 > 10) Input: root = [8,3,10,1,6,null,14,null,null,4,7] Output: true

نفكّر فيها مع بعض

  1. الجديد هنا: لحد دلوقتي كنا بنثق إن الـ tree BST. هنا بنتحقق، وبنبعت معلومة من فوق لتحت (الـ range المسموح).
  2. أول حل بييجي في دماغ أي حد (وهو غلط): لكل node، اتأكد إن ابنها الشمال أصغر وابنها اليمين أكبر، وكمّل recursive. ده بالظبط الـ check المحلي اللي شفناه في الـ animation فوق، وبيقول true على [10,5,15,2,12].
  3. إيه اللي ناقص؟ الـ 12 لازم تبقى أكبر من 5 (أبوها)، وكمان أصغر من 10 (جدها، لأنها نزلت شماله). يعني كل node عليها شروط من كل الـ ancestors، مش من أبوها بس.
  4. الفكرة: كل node ليها range مسموح (low, high). الـ root مسموحلها أي حاجة: (-∞, ∞). لما ننزل شمال node قيمتها v، الـ high بيبقى v، لأن كل الشمال لازم أصغر منها. ولما ننزل يمين، الـ low بيبقى v. والـ range بيضيق كل ما ننزل، وبيشيل معاه شروط كل الـ ancestors.
  5. حل تاني صح: نفس فكرة Kth Smallest: الـ inorder لازم يطلع تصاعدي strictly. نمشي inorder ونقارن كل قيمة باللي قبلها. هنكتبه تحت كمان.
  6. الحالات الطرفية: node واحدة (true). قيم متساوية [2,2,2] (false، لأن الـ strict). قيم عند حدود الـ int زي 2147483647 (لازم الحل ما يعتمدش على رقم "كبير" معيّن).
  1. دالة جوه دالة عشان نضيف parameters (low و high) من غير ما نغيّر الـ signature اللي LeetCode طالبها. الـ range مفتوح من الناحيتين: القيمة لازم أكبر من low وأصغر من high، مش بتساويهم.
  2. الـ subtree الفاضية BST صح دايمًا. وده كمان الـ base case اللي بيوقف الـ recursion.
  3. ليه <= و >=؟ المسألة strict: قيمة بتساوي الـ low أو الـ high معناها تكرار. [2,2,2] لازم ترجع false، ولو كتبت < هترجّع true.
  4. ننزل شمال بنفس الـ low اللي جالنا من فوق، والـ high بيبقى قيمة الـ node. الـ low ما اتغيّرش، لأن الشروط القديمة لسه سارية على الشمال كمان.
  5. نفس الكلام يمين: الـ low بيبقى قيمة الـ node والـ high زي ما هو. والـ && بتعمل short-circuit: لو الشمال طلع false، اليمين مش هيتشيّك خالص، ودي توفيرة مجانية.
  6. ليه -Infinity و Infinity؟ عشان أي قيمة حقيقية تبقى جوه. اللي بيكتب INT_MIN في C++ بيقع في test فيه node قيمتها -2147483648، لأن node.val <= low بتطلع true. في C++ استخدم long long.

شوف الحل على نفس الـ tree اللي خدعت الـ check المحلي. الرقم تحت كل node هو الـ range المسموح ليها:

Inputالمتوقعليه الحالة دي مهمة
[10,5,15,2,12]falseبيكسّر الحل اللي بيقارن بالأب بس
[2,2,2]falseبيكسّر < بدل <=
[2147483647]trueبيكسّر الحلول اللي بتستخدم INT_MAX كـ high
[5,4,6,null,null,3,7]falseالـ 3 في يمين الـ 5 بس أصغر منها: نفس الغلطة من الناحية التانية
[1]truenode واحدة

التعقيد: في أسوأ حالة (tree صح) بنزور كل node مرة، فالوقت O(n). الـ memory O(h) للـ recursion.

في الانترفيو المسألة دي معمولة مخصوص عشان تشوف هتقع في الحل المحلي ولا لأ. ابدأ بإنك تقول: "مش كفاية أقارن بالأب، لأن الـ node لازم تحترم كل الـ ancestors"، وارسم مثال زي [10,5,15,2,12]. ده لوحده بيقول للـ interviewer إنك فاهم القاعدة.

كل المسائل اللي فاتت الـ tree كانت جاهزة. آخر مثال: هنبنيها بإيدينا من array.

مثال محلول 6: Convert Sorted Array to BST

Convert Sorted Array to Binary Search Tree

easyLeetCode 108

عندك array مترتبة تصاعدي. ابني منها BST متوازنة: عند كل node، فرق الـ height بين الشمال واليمين بالكتير 1.

Input: nums = [1, 3, 4, 6, 7, 10, 14] Output: [6,3,10,1,4,7,14] (one valid answer; others exist)

نفكّر فيها مع بعض

  1. الجديد هنا: كل اللي فات الـ tree كانت موجودة. هنا بنبنيها من الصفر، والـ recursion بيقسم range زي الـ binary search.
  2. لو ضفناهم بالترتيب بالـ insert، هتطلع الـ tree المايلة اللي شفناها فوق. ده عكس المطلوب.
  3. مين يبقى الـ root؟ عشان الشمال واليمين يبقوا قد بعض، لازم الـ root يكون العنصر اللي في النص. ساعتها نص العناصر أصغر منه (يروحوا شمال)، والنص أكبر (يروحوا يمين).
  4. وبعدين؟ النص الشمال نفسه array مترتبة، فنبني منه BST متوازنة بنفس الطريقة: النص بتاعه يبقى root الشمال. ده recursion، وهو نفس تقسيم الـ binary search بالظبط.
  5. بدل ما نقطّع الـ array بـ slice (كل slice بتعمل نسخة وتاخد وقت)، نبعت حدود الجزء: lo و hi.
  6. الحالات الطرفية: عنصر واحد، عنصرين (الـ mid هيبقى الأول، والتاني هيروح يمين)، عدد زوجي.
  1. الحدود inclusive من الناحيتين: lo و hi الاتنين جوه الجزء. القرار ده بيحدد كل حاجة بعده، فاكتبه كـ comment دايمًا.
  2. ليه lo > hi مش lo >= hi؟ لما lo === hi فيه عنصر واحد في الجزء، ولازم يبقى node (leaf). لو كتبت >= هترمي كل الـ leaves، والـ tree هتطلع ناقصة. الجزء فاضي بس لما lo يعدّي hi.
  3. (lo + hi) >> 1 هي Math.floor((lo + hi) / 2) (التفاصيل في فصل الـ bits). لو العدد زوجي بياخد النص الشمال، وده متوازن برضه.
  4. الـ node بتاعة النص.
  5. ليه mid - 1؟ عشان الـ mid نفسه اتاخد خلاص. لو كتبت build(lo, mid)، الـ mid هيتحط تاني في الشمال، ولما الجزء يبقى عنصرين هيلف للأبد (mid هيفضل lo).
  6. نفس الكلام: mid + 1 عشان نبدأ بعده.
  7. nums.length - 1 مش nums.length، عشان الحدود inclusive. لو كتبت nums.length، آخر node هتبقى nums[n] وهي undefined.

ليه النتيجة متوازنة؟ عند كل node، الشمال فيه mid - lo عنصر واليمين فيه hi - mid، والفرق بينهم بالكتير 1. فالـ heights مش ممكن تبعد عن بعض أكتر من 1.

التعقيد: كل عنصر بيبقى node مرة واحدة، فالوقت O(n). الـ memory O(log n) للـ recursion، لأن الـ tree متوازنة، غير الـ tree نفسها اللي هي الإجابة.

شفت كام مكان ممكن سطر واحد يغلّطك فيه؟ يلا نجمعهم.

غلطات مشهورة

معظم الغلطات دي بتعدّي من الـ examples اللي في المسألة، وبتقع في الـ hidden tests. عشان كده لازم تعرفها قبل ما تقع فيها.

1. تقارن الـ node بأولادها المباشرين بس

القاعدة على كل الـ subtree. الحل: ابعت low و high من فوق، أو اتأكد إن الـ inorder تصاعدي strictly.

2. نسيت تربط النتيجة في الـ recursive insert أو delete

لما root.left يبقى null، الـ call بترجّع node جديدة ومحدش بيمسكها. لازم root.left = insertIntoBST(root.left, val). القاعدة: لو الدالة بترجّع root جديد، لازم حد يكتبه في مكان.

3. تحط حدود "كبيرة" بدل Infinity

الـ LeetCode حاطط test فيه القيمة دي مخصوص. استخدم -Infinity و Infinity في JS.

4. في الـ delete بحالة الابنين، تمسح الـ key بدل الـ successor

بعد ما نسخت قيمة الـ successor فوق، اللي محتاج يتمسح تحت هو الـ successor القديم، يعني succ.val. الـ key مش موجود في اليمين أصلًا (كان في الـ node اللي فوق).

5. off-by-one في الـ k

كل ما المسألة تقول "kth" أو "رقم k"، اسأل نفسك: الـ k بيبدأ من 1 ولا من 0؟ في Kth Smallest بيبدأ من 1، فأول عنصر هو sorted[0]. جرّب k = 1 في دماغك قبل ما تسلّم.

6. تقول O(log n) على أي BST

الـ BST مش متوازنة لوحدها. لو الداتا جاية مترتبة، الـ tree هتبقى خط مايل، وكل عملية O(n). قول O(h)، ووضّح الحالتين.

دلوقتي جرّب نفسك: كام سؤال سريع، وتمرين تفكّر فيه قبل ما تفتح الحل.

اختبر نفسك

أنهي tree فيهم BST صح؟ (مكتوبين مستوى مستوى زي LeetCode)

  • [5,3,8,1,6,7,9]
  • [5,3,8,1,4,7,9]
  • [5,3,8,1,4,2,9]
  • [5,5,8]

في الأولى الـ 6 في شمال الـ 5 وهي أكبر منها. في التالتة الـ 2 في يمين الـ 5 وهي أصغر منها (كل واحدة فيهم تمام مع أبوها المباشر، وده الفخ). والرابعة فيها تكرار، والقاعدة strict.

ضفت الأرقام من 1 لـ n بالترتيب في BST فاضية. الـ search على n بياخد كام؟

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n)

كل رقم أكبر من كل اللي قبله، فبيروح يمين لآخر الطريق. الـ tree بتبقى خط مايل طوله n، فالـ h = n، والـ search على آخر رقم بيعدّي على الـ n كلهم.

بتمسح node ليها ابنين. أنهي قيمة تاخد مكانها والقاعدة تفضل صح؟

  • ابنها الشمال المباشر
  • ابنها اليمين المباشر
  • أصغر قيمة في الـ right subtree
  • أكبر قيمة في الـ right subtree

أصغر قيمة في اليمين (الـ successor) أكبر من كل الشمال، لأنها في اليمين، وأصغر من كل اليمين الباقي، لأنها أصغرهم. الابن اليمين المباشر ممكن يكون عنده ابن شمال أصغر منه، فلو حطيته فوق، الابن ده هيبقى في اليمين وهو أصغر. ممنوع.

في Validate بالحدود، إحنا عند node قيمتها 20 والـ range بتاعها (10, 30). الـ range بتاع ابنها الشمال إيه؟

  • (-∞, 20)
  • (10, 20)
  • (10, 30)
  • (20, 30)

الـ low بيفضل 10، لأن الشرط ده جاي من ancestor فوق ولسه ساري. والـ high بيبقى 20، لأن الشمال لازم أصغر من الـ node. الـ range بيضيق بس، عمره ما بيوسع.

Kth Smallest بالـ stack والوقوف بدري، على tree متوازنة فيها مليون node و k = 5. هيلمس كام node تقريبًا؟

  • مليون
  • نص مليون
  • حوالي 25: الـ h (حوالي 20) + الـ k
  • 5 بالظبط

الأول بينزل من الـ root لأقصى الشمال، ده حوالي h = 20 node. وبعدين بيطلّع 5 عناصر بس ويقف. عشان كده الـ complexity O(h + k).

تمرين: فكّر قبل ما تفتح

Range Sum of BST

easyLeetCode 938

رجّع مجموع كل القيم في الـ BST اللي بين low و high (الاتنين داخلين). حاول ما تلفّش على الـ tree كلها لو مش لازم.

root = [8,3,10,1,6,null,14,null,null,4,7], low = 4, high = 8 → 25 (4 + 6 + 7 + 8)
تلميح 1

DFS عادي على كل الـ tree هيشتغل، O(n). بس فكّر: لو node قيمتها أصغر من low، إيه رأيك في كل اللي في شمالها؟

تلميح 2

لو node.val < low، الـ node نفسها برا، وكل شمالها أصغر منها فبرا برضه. يبقى نروح يمين بس. ولو node.val > high، نروح شمال بس. غير كده الـ node جوه، ونجمعها ونروح الناحيتين.

الحل

لاحظ < و > مش <= و >=: الحدود داخلة في المجموع، فالـ node اللي قيمتها low بالظبط لازم تتجمع. الوقت في أسوأ حالة O(n) (لو كل القيم جوه الـ range)، بس لو الـ range ضيق، بنرمي subtrees كاملة من غير ما نلمسها.

لو الأسئلة عدّت معاك، روح على LeetCode بالترتيب اللي تحت.

اتمرن على LeetCode بالترتيب

حلها بالترتيب ده، كل مسألة بتضيف فكرة واحدة جديدة. لو قعدت أكتر من 25 دقيقة على مسألة، ارجع للقالب بتاعها هنا، وبعدين حاول تاني من غير ما تبص.

وآخر حاجة: الفصل كله في صفحة واحدة ترجعلها قبل أي انترفيو.

الخلاصة

في جملة واحدة الـ BST هي binary tree كل الشمال فيها أصغر وكل اليمين أكبر عند كل node. القاعدة دي بتديك حاجتين: كل مقارنة بترمي subtree كاملة (فالعمليات O(h))، والـ inorder بيطلع مترتب.
السؤالالإجابة
القاعدة على مين؟على كل الـ subtree، مش الأولاد المباشرين بس.
Complexity الـ search والـ insert والـ delete؟O(h): حوالي O(log n) لو متوازنة، و O(n) لو مايلة.
محتاج القيم مترتبة أو رقم k؟inorder: شمال، node، يمين. بالـ stack لو عايز تقف بدري.
بتمسح node ليها ابنين؟انسخ قيمة الـ successor (أقصى الشمال في اليمين)، وامسحه هو من اليمين.
حدود الـ validate؟-Infinity و Infinity، والمقارنة <= / >= عشان التكرار ممنوع.
بتبني من array مترتبة؟النص root، والـ recursion على [lo, mid - 1] و [mid + 1, hi]، وتقف لما lo > hi.

الفصل الجاي: الـ BST مترتبة بالكامل، وده بيكلّف: كل insert محتاج يلاقي المكان الصح بالظبط، والـ tree ممكن تميل. طب لو كل اللي محتاجه هو أصغر عنصر بس، كل شوية؟ في Heap و Priority Queue هتشوف tree بقاعدة أضعف بكتير (الأب أصغر من أولاده وخلاص)، بس متوازنة دايمًا ومتخزّنة في array عادية، فالـ insert والـ pop بيبقوا O(log n) مضمونين.