كيفية تطبيق خوارزميات Binary Tree في المقابلات التقنية

مقدمة إلى خوارزميات Binary Tree في المقابلات التقنية

تُعد Binary Tree من أشهر هياكل البيانات في تطوير البرمجيات، كما أنها من الموضوعات المتكررة في technical interviews. لذلك فإن إتقان أساسياتها لا يساعدك فقط على حل الأسئلة النظرية، بل يمنحك أيضاً قدرة أفضل على كتابة حلول عملية في المشاريع البرمجية.

يستعرض هذا المقال المفاهيم الأساسية المرتبطة بـ Binary Tree، ثم يوضح أهم الخوارزميات المرتبطة بها مثل Depth First Traversal وBreadth First Traversal وعمليات البحث والحساب على الشجرة، مع التركيز على طريقة التفكير المطلوبة في المقابلات التقنية.

ما هي Binary Tree؟

Binary Tree هي بنية بيانات تتكون من مجموعة من nodes، حيث يمكن لكل node أن تشير إلى أبناء آخرين عبر edges. في الحالة الخاصة بـ Binary Tree، لا يمكن لأي node أن تمتلك أكثر من ابنين.

لفهمها جيداً، من المهم التعرف إلى المصطلحات الأساسية التالية:

• Root: العقدة التي لا تمتلك أباً.
• Parent: العقدة التي تتفرع منها عقد أخرى.
• Child: العقدة التابعة لعقدة أعلى منها.
• Leaf: العقدة التي لا تمتلك أي أبناء.
• Path: سلسلة من العقد المتصلة يمكن الانتقال خلالها من عقدة إلى أخرى.

متى تكون الشجرة من نوع Binary Tree؟

حتى نعتبر البنية Binary Tree بالمعنى البرمجي الكلاسيكي، ينبغي تحقق الشروط التالية:

1. كل node تملك بحد أقصى طفلين فقط.
2. توجد Root واحدة فقط.
3. يوجد مسار وحيد فقط بين root وأي node داخل الشجرة.

هذه الشروط مهمة جداً في المقابلات، لأن بعض الأسئلة لا تُصرّح مباشرة بأن البنية المعطاة هي Binary Tree، بل تتوقع منك اكتشاف ذلك من شكل العلاقات بين العقد.

الصورة السابقة تمثل بنية لا يغطيها هذا النوع من الشرح، لأنها لا تتوافق مع النموذج المقصود في خوارزميات Binary Tree التقليدية.

لماذا تُطرح Binary Tree كثيراً في المقابلات التقنية؟

السبب بسيط: هذا النوع من الهياكل يختبر أكثر من مهارة في الوقت نفسه، مثل:

• فهم هياكل البيانات.
• القدرة على استخدام recursion.
• تحليل التعقيد الزمني والمكاني.
• التمييز بين DFS وBFS.
• القدرة على تحويل الفكرة النظرية إلى كود واضح وصحيح.

كما أن مسائل الأشجار تساعد المحاور على تقييم طريقة تفكيرك، وليس فقط النتيجة النهائية التي تصل إليها.

تمثيل Binary Tree برمجياً

غالباً ما يتم تمثيل كل node داخل Binary Tree ككائن يحتوي على:

• القيمة الحالية val
• مؤشر إلى الابن الأيسر left
• مؤشر إلى الابن الأيمن right

وعندما لا يوجد ابن في أحد الاتجاهين، يتم تخزين قيمة مثل null.

مثال على تعريف Node في JavaScript

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

مثال على بناء Binary Tree يدوياً

const a = new Node('a');
const b = new Node('b');
const c = new Node('c');
const d = new Node('d');
const e = new Node('e');
const f = new Node('f');

a.left = b;
a.right = c;
b.left = d;
b.right = e;
c.right = f;

هذا التمثيل البسيط يكفي لتجربة معظم خوارزميات الأشجار أثناء التعلم أو أثناء التدريب على أسئلة المقابلات.

أهم الموضوعات التي يجب إتقانها في Binary Tree

خوارزمية Depth First Traversal

في Depth First Traversal نتحرك إلى أعمق مستوى ممكن أولاً، ثم نعود تدريجياً لمعالجة الفروع الأخرى. في شجرة نموذجية، قد يكون ترتيب الزيارة بالشكل التالي:

A, B, D, E, C, F

متى نستخدم Depth First Traversal؟

• عند الحاجة إلى استكشاف فرع كامل قبل الانتقال إلى فرع آخر.
• عند كتابة حلول تعتمد على recursion.
• في مسائل مثل حساب المجموع أو إيجاد أكبر مسار أو التحقق من وجود قيمة.

التنفيذ التكراري باستخدام Stack

الإصدار التكراري من DFS يعتمد على stack. الفكرة الأساسية:

1. ضع root في stack.
2. طالما أن stack غير فارغ، أخرج العقدة العليا.
3. أضف قيمتها إلى النتيجة.
4. ادفع أبناءها إلى stack مع مراعاة ترتيب left وright.

const depthFirstValues = (root) => {
  if (root === null) return [];

  const result = [];
  const stack = [root];

  while (stack.length > 0) {
    const current = stack.pop();
    result.push(current.val);

    if (current.right) stack.push(current.right);
    if (current.left) stack.push(current.left);
  }

  return result;
};

التنفيذ باستخدام Recursion

الإصدار العودي أنيق جداً في مسائل الأشجار، لأنه يستفيد من call stack بشكل طبيعي.

const depthFirstValues = (root) => {
  if (root === null) return [];

  const leftValues = depthFirstValues(root.left);
  const rightValues = depthFirstValues(root.right);

  return [root.val, ...leftValues, ...rightValues];
};

تحليل التعقيد

• Time Complexity: O(n)
• Space Complexity: O(n)

خوارزمية Breadth First Traversal

في Breadth First Traversal نتحرك أفقياً عبر مستويات الشجرة قبل النزول إلى المستوى التالي. إذا كانت الشجرة تحتوي على العقد A وB وC وD وE وF، فقد يكون الترتيب:

A, B, C, D, E, F

متى نستخدم Breadth First Traversal؟

• عند الحاجة إلى معالجة الشجرة مستوى بمستوى.
• في المسائل التي تتعلق بأقرب العناصر أو ترتيب المستويات.
• عندما يكون ترتيب المستويات مهماً أكثر من التعمق داخل الفروع.

التنفيذ باستخدام Queue

const breadthFirstValues = (root) => {
  if (root === null) return [];

  const values = [];
  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    values.push(current.val);

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }

  return values;
};

تحليل التعقيد

• Time Complexity: O(n)
• Space Complexity: O(n)

ملاحظة تقنية: في بعض اللغات مثل JavaScript، استخدام shift() على المصفوفة قد لا يكون مثالياً من ناحية الأداء، لذلك في التطبيقات الكبيرة قد يكون من الأفضل استخدام بنية queue أكثر كفاءة.

التحقق من وجود قيمة داخل الشجرة: Tree Includes

هذا النوع من الأسئلة يطلب منك إرجاع true أو false حسب وجود قيمة معينة داخل Binary Tree.

حل Breadth First

const treeIncludes = (root, target) => {
  if (root === null) return false;

  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    if (current.val === target) return true;

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }

  return false;
};

حل Recursive باستخدام Depth First

const treeIncludes = (root, target) => {
  if (root === null) return false;
  if (root.val === target) return true;

  return treeIncludes(root.left, target) || treeIncludes(root.right, target);
};

الميزة هنا أن النسخة العودية قصيرة وواضحة جداً، لكنها تتطلب فهماً جيداً لطريقة عمل recursion.

حساب مجموع القيم داخل الشجرة: Tree Sum

في هذا النوع من المسائل نمر على جميع العقد ونجمع قيمها. إذا كانت العقد تحتوي على أرقام، فالحل الطبيعي يكون إما عبر DFS أو BFS.

الحل العودي

const treeSum = (root) => {
  if (root === null) return 0;
  return root.val + treeSum(root.left) + treeSum(root.right);
};

الحل التكراري باستخدام Queue

const treeSum = (root) => {
  if (root === null) return 0;

  let totalSum = 0;
  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    totalSum += current.val;

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }

  return totalSum;
};

إيجاد أصغر قيمة داخل الشجرة: Tree Min Value

هذه المسألة تقيس قدرتك على الاحتفاظ بقيمة دنيا أثناء المرور على العقد، أو إعادة بناء الإجابة بشكل عودي.

الحل التكراري

const treeMinValue = (root) => {
  let smallest = Infinity;
  const queue = [root];

  while (queue.length > 0) {
    const current = queue.shift();
    if (current.val < smallest) smallest = current.val;

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  }

  return smallest;
};

الحل العودي

const treeMinValue = (root) => {
  if (root === null) return Infinity;

  const leftMin = treeMinValue(root.left);
  const rightMin = treeMinValue(root.right);

  return Math.min(root.val, leftMin, rightMin);
};

استخدام Infinity هنا ليس تفصيلاً عابراً، بل حيلة منطقية ممتازة تجعل التعامل مع الفروع الفارغة أسهل وأكثر نظافة.

إيجاد أكبر مجموع من Root إلى Leaf

هذا السؤال من أكثر الأسئلة المفيدة في المقابلات، لأنه يجمع بين فهم المسارات وrecursion واتخاذ القرار بين فرعين.

الفكرة هي حساب أكبر مجموع ممكن يبدأ من root وينتهي عند أي leaf.

المنطق العام للحل

• إذا كانت العقدة leaf، فأعد قيمتها مباشرة.
• إذا وصلت إلى فرع غير موجود، فأعد -Infinity.
• في كل خطوة، خذ أكبر نتيجة بين الفرع الأيسر والفرع الأيمن، ثم أضف قيمة العقدة الحالية.

الحل البرمجي

const maxPathSum = (root) => {
  if (root === null) return -Infinity;
  if (root.left === null && root.right === null) return root.val;

  const maxChildPathSum = Math.max(
    maxPathSum(root.left),
    maxPathSum(root.right)
  );

  return root.val + maxChildPathSum;
};

هذا الحل يظهر بوضوح كيف يمكن دمج أكثر من فكرة سبق تعلمها: base case، والمقارنة باستخدام Math.max، والتعامل مع الشجرة الفارغة كحالة خاصة.

نصائح عملية لاجتياز أسئلة Binary Tree في المقابلات

1) ابدأ برسم الشجرة

حتى لو كان السؤال شفهياً، فإن رسم nodes وedges يساعدك على فهم العلاقات بسرعة واكتشاف الحالات الخاصة.

2) حدّد نوع المرور المطلوب

اسأل نفسك مبكراً:

• هل أحتاج إلى DFS أم BFS؟
• هل المسألة تتعلق بمستويات الشجرة أم بمسار داخلها؟
• هل recursion سيجعل الحل أوضح؟

3) لا تنس الحالات الطرفية

من أكثر أسباب الأخطاء شيوعاً:

• نسيان حالة null
• نسيان الشجرة الفارغة
• الخلط بين root وleaf
• عدم التحقق من وجود left أو right قبل الوصول إليهما

4) اشرح التعقيد بوضوح

في المقابلات لا يكفي أن تكتب الكود، بل يجب أن تشرح لماذا يكون التعقيد غالباً:

• O(n) زمنياً لأنك تزور كل عقدة مرة واحدة.
• O(n) مكانياً بسبب stack أو queue أو call stack.

5) تدرب على النسختين: iterative و recursive

بعض الأسئلة يكون الحل العودي فيها أوضح، وبعضها يفضّل فيه المحاور رؤية فهمك لـ stack أو queue بشكل صريح.

متى تستخدم DFS ومتى تستخدم BFS؟

كيف تجعل إجابتك أقوى أمام المحاور؟

بدلاً من القفز مباشرة إلى الكود، اتبع هذا التسلسل:

1. عرّف المشكلة بلغة بسيطة.
2. اشرح نوع البنية: هل هي Binary Tree فعلاً؟
3. حدّد إن كنت ستستخدم stack أو queue أو recursion.
4. اذكر base cases بوضوح.
5. اكتب الكود خطوة بخطوة.
6. اختبر الحل ذهنياً على مثال صغير.
7. اختم بتحليل التعقيد.

هذا الأسلوب لا يجعل إجابتك صحيحة فقط، بل يجعلك تبدو منظماً وواثقاً، وهي نقطة مهمة جداً في المقابلات التقنية.

الخلاصة التقنية

فهم Binary Tree لا يقتصر على حفظ تعريفات مثل root وleaf، بل يعتمد على القدرة على اختيار أسلوب المرور المناسب، وبناء base cases صحيحة، وتحويل الفكرة إلى كود واضح وآمن من الأخطاء. من الناحية العملية، فإن إتقان Depth First Traversal وBreadth First Traversal هو الأساس الذي تُبنى عليه غالبية مسائل الأشجار في المقابلات. وإذا أتقنت أنماطاً مثل Tree Includes وTree Sum وTree Min Value وMax Root to Leaf Path Sum، فستكون جاهزاً للتعامل مع طيف واسع من الأسئلة المشابهة بثقة أكبر ومنهجية أوضح.