[May 19 - May 26]

Test, Debug, Code, Advance! + Binary Search Tree insert() and search()

Coding info

I have several updates this week! I tested my code for the C++ backend of class: Node, TreeNode, ArrayForTrees and BinaryTree. There were a few bugs and Segmentation Faults, but I successfully managed to fix all of them 🙂 ! This week, I also worked on search() and insert() functions of a new class: BinarySearchTree.

What’s working

As its been 3 weeks of my GSoC, I proudly present to you everything that I have done till now, and tested for correctness. Here’s the working product of the 1100 lines of code that I wrote till now:

TreeNode C++ backend test:

def test_cpp_TreeNode():
    n = TreeNode(1,100,backend=Backend.CPP)
    assert str(n) == "(None, 1, 100, None)"

BinaryTrees C++ backend test:

def test_cpp_BinaryTree():
    b = BinaryTree(1,100,backend=Backend.CPP)
    assert raises(NotImplementedError, b.insert) # Correctly throws NotImplementedError: This is an abstract method
    assert raises(NotImplementedError, b.delete) # Correctly throws NotImplementedError: This is an abstract method
    assert raises(NotImplementedError, b.search) # Correctly throws NotImplementedError: This is an abstract method
    assert str(b) == "[(None, 1, 100, None)]"

ArrayForTrees C++ backend test:

def test_cpp_ArrayForTrees():
    from pydatastructs.linear_data_structures._backend.cpp import _arrays
    from pydatastructs.utils._backend.cpp import _nodes
    AFT = _arrays.ArrayForTrees
    root = TreeNode(1, 100, backend=Backend.CPP)
    A = AFT(_nodes.TreeNode, [root])
    assert str(A) == "['(None, 1, 100, None)']"
    node = TreeNode(2, 200, backend=Backend.CPP)
    A.append(node)
    assert str(A) == "['(None, 1, 100, None)', '(None, 2, 200, None)']"

BinarySearchTree C++ backend test: (This is still a work in progress)

search()

def test_cpp_BinarySearchTree_search():
    b = BinarySearchTree(1,100, backend=Backend.CPP)
    assert str(b) == "[(None, 1, 100, None)]"
    assert b.search(1) == 0
    assert b.search(1,parent=False) == 0
    assert b.search(1,parent=True) == (0, None)

insert()

def test_cpp_BinarySearchTree_insert():
    BST = BinarySearchTree
    b = BST(8, 8, backend=Backend.CPP)
    b.insert(3, 3)
    b.insert(10, 10)
    b.insert(1, 1)
    b.insert(6, 6)
    b.insert(4, 4)
    b.insert(7, 7)
    b.insert(14, 14)
    b.insert(13, 13)
    assert str(b) == \
    ("[(1, 8, 8, 2), (3, 3, 3, 4), (None, 10, 10, 7), (None, 1, 1, None), "
    "(5, 6, 6, 6), (None, 4, 4, None), (None, 7, 7, None), (8, 14, 14, None), "
    "(None, 13, 13, None)]")

Relevant PRs:

I worked on the PR: #556

There have been a plethora of commits to this PR. Commits of this week focused on testing my implementations in class Node, TreeNode, ArrayForTrees, BinaryTree and adding the BinarySearchTree class methods: insert() and search().

Here is the progress tracker for the next few weeks: #554

In the following week, I will add more functionality to the BinarySearchTree class. This includes methods like delete(), upper_bound(), lower_bound(), lowest_common_ancestor() and many more!

Learnings/Difficulties

Most importantly, this week taught me to persevere, and brainstorm to fix every segmentation fault encountered. I learned to be patient and trust the process, and this was truely rewarding!


I am grateful to my mentor, Gagandeep Singh, for helping me whenever requested.

See you again after productive 7 days! :)