Binary search trees

English

A binary search tree (BST) stores values so they stay sorted and are fast to find.
Each node holds a value and links to up to two children: a left and a right.
The top node is the root. A node with no children is a leaf.

العربية

أشجار البحث الثنائية

شجرة البحث الثنائية (BST) تخزن قيمًا بحيث تبقى مرتبة وسهلة العثور عليها.
كل عقدة تحمل قيمة وترتبط بما يصل إلى طفلين: left وright.
العقدة العليا هي الجذر. عقدة بدون أطفال هي ورقة.

English

The BST rule

For every node: everything in its left subtree is smaller, everything in its right is larger.
This one rule is what lets you find a value by going left or right — never both.

العربية

قاعدة شجرة البحث الثنائية

لكل عقدة: كل شيء في الشجرة الجانبية اليسرى أصغر، وكل شيء في الشجرة الجانبية اليمنى أكبر.
هذه القاعدة الوحيدة هي ما يسمح لك بإيجاد قيمة بالذهاب يسارًا أو يمينًا — لا كليهما.

        5
       / \
      3   8
     / \   \
    1   4   9

left < node < right, at every node

English

A node

We model a node as a small object with a value, a left, and a right.
A brand-new node has no children yet, so left and right start as None.

العربية

العقدة

نمذج العقدة ككائن صغير يحتوي على value، وleft، وright.
العقدة الجديدة تماماً ليس لها أطفال بعد، لذا left وright تبدأان كـNone.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

n = Node(5)
print(n.value)   # 5
print(n.left)    # None

English

Inserting a value

Start at the root. If the tree is empty, the new value becomes the root.
If the value is smaller than the current node, go left; otherwise go right.
Repeat until you reach an empty spot, and put the new node there.

العربية

إدخال قيمة

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

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

root = None
for v in [5, 3, 8, 1]:
    root = insert(root, v)
print(root.value)            # 5
print(root.left.value)       # 3
print(root.right.value)      # 8

English

In-order traversal gives sorted order

In-order traversal visits: the left subtree, then the node, then the right subtree.
Because of the BST rule, this visits the values in sorted order — for free.
It is naturally recursive: traverse left, take the value, traverse right.

العربية

المسار الترتيبي يعطي ترتيبًا مرتبًا

الترتيب الداخلي يزور: الفرع الأيسر، ثم العقدة، ثم الفرع الأيمن.
بسبب قاعدة شجرة البحث الثنائي (BST)، يتم زيارة القيم بترتيب مرتبط — مجاناً.
هي بطبيعتها تكرارية: traversal يسار، خذ القيمة، traversal يمين.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    if root is None:
        return []
    return in_order(root.left) + [root.value] + in_order(root.right)

root = None
for v in [5, 3, 8, 1, 4]:
    root = insert(root, v)
print(in_order(root))   # [1, 3, 4, 5, 8]

English

Searching is fast

To find a value, compare it with the node, then go left or right — skipping half the tree each step.
In a balanced tree this takes about O(log n) steps, much faster than scanning a list.
A badly-shaped tree (values inserted already sorted) can degrade to a line — O(n).

العربية

البحث سريع

لإيجاد قيمة، قارنها بالعقدة، ثم اذهب يسار أو يمين — متجاوزاً نصف الشجرة في كل خطوة.
في شجرة متوازنة يستغرق ذلك حوالي O(log n) خطوات، أسرع بكثير من مسح قائمة.
شجرة سيئة الشكل (قيم مُدرجة مسبقاً) يمكن أن تتدهور إلى خط — O(n).

English

Common mistakes

In a binary search tree: left child < node < right child.
An unbalanced tree loses the speed advantage.

العربية

أخطاء شائعة

في شجرة بحث ثنائية: الطفل الأيسر < العقدة < الطفل الأيمن.
الشجرة غير المتوازنة تفقد ميزة السرعة.

English

Now you try

Build the three core operations: insert, in_order, and contains.
The Node class (and a working insert, where you need it) is provided.
Press Check answer to test it on several trees.

العربية

الآن جرب بنفسك

بنِ العمليات الأساسية الثلاث: insert، in_order، وcontains.
تم توفير فصل Node (وفصل insert يعمل، حيث تحتاجه).
اضغط تحقق من الإجابة لاختباره على عدة أشجار.

Explore · ⁨استكشف⁩

Searching a BST · ⁨البحث في شجرة BST⁩

Left is smaller, right is bigger — so each step skips half the tree. · ⁨الأيسر أصغر، والأيمن أكبر — لذا كل خطوة تتجاوز نصف الشجرة.⁩

The Node class is provided. Write insert(root, value) that adds value to the BST and returns the root. If root is None, return a new Node(value). If value < root.value go left, otherwise go right — and reassign that child to the result of inserting into it. · ⁨فئة Node مُقدَّمة. اكتب insert(root, value) التي تضيف value إلى شجرة BST وتُرجع الجذر. إذا كان root هو None، أرجع Node(value) جديداً. إذا كان value < root.value اذهب يساراً، وإلا اذهب يميناً — وأعد تعيين ذلك الابن لناتج الإدراج فيه.⁩

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    # Empty -> new Node. Else go left if smaller, right otherwise. Return root.
    pass

Click Run to see the output here. · ⁨اضغط تشغيل لرؤية المخرجات هنا.⁩

Node and a working insert are provided. Write in_order(root) that returns a list of the values from an in-order traversal: left subtree, then this node's value, then right subtree. Thanks to the BST rule the list comes out sorted. An empty tree (None) gives []. · ⁨Node وinsert تعملان مُقدَّمان. اكتب in_order(root) الذي يُرجع قائمة من القيم من خلال traversal ترتيبية: الفرع الأيسر، ثم قيمة هذا العقدة، ثم الفرع الأيمن. بفضل قاعدة BST تظهر القائمة مرتبة. شجرة فارغة (None) تُعطي [].⁩

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def in_order(root):
    # Return left values + [this value] + right values; [] when root is None
    pass

Click Run to see the output here. · ⁨اضغط تشغيل لرؤية المخرجات هنا.⁩

Node and a working insert are provided. Write contains(root, value) that returns True if value is in the tree, else False. Use the BST rule: if it equals this node return True; if it is smaller search left, otherwise search right; an empty branch (None) means it is not there. · ⁨Node وinsert تعملان مُقدَّمان. اكتب contains(root, value) الذي يُرجع True إذا كان value في الشجرة، وإلا False. استخدم قاعدة BST: إذا تساوي هذا العقدة أرجع True؛ إذا كانت أصغر ابحث يساراً، وإلا ابحث يميناً؛ فرع فارغ (None) يعني أنه غير موجود.⁩

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def insert(root, value):
    if root is None:
        return Node(value)
    if value < root.value:
        root.left = insert(root.left, value)
    else:
        root.right = insert(root.right, value)
    return root

def contains(root, value):
    # None -> False. Equal -> True. Smaller -> search left, else search right.
    pass

Click Run to see the output here. · ⁨اضغط تشغيل لرؤية المخرجات هنا.⁩

Binary search trees · ⁨أشجار البحث الثنائية⁩