Conversation
Non linear data structures
There was a problem hiding this comment.
Pull request overview
This PR adds a Binary Search Tree implementation to a repository containing various non-linear data structures. The PR includes a README file and a complete BST implementation with insertion, removal, and three types of tree traversal (in-order, pre-order, post-order).
Changes:
- Added README.md with repository title
- Implemented Binary Search Tree with Node class and BinarySearchTree class
- Included example usage demonstrating insertion, removal, and traversal operations
Reviewed changes
Copilot reviewed 2 out of 2 changed files in this pull request and generated 11 comments.
| File | Description |
|---|---|
| README.md | Added repository title "Non Linear Data Structures" |
| BinarySearchTree/binarySearchTree.py | Complete BST implementation with insert, remove, and traversal methods, plus example usage |
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
| self.right_node = None | ||
|
|
||
|
|
||
| class BinarySearchTree: |
There was a problem hiding this comment.
Missing docstring for the BinarySearchTree class. Adding a docstring would improve code documentation and explain the purpose of this class, its invariants (BST property), and available operations.
| class BinarySearchTree: | |
| class BinarySearchTree: | |
| """ | |
| Binary Search Tree (BST) implementation storing comparable values. | |
| The tree maintains the BST invariant: for any given node, all values in | |
| the left subtree are strictly less than the node's value, and all values | |
| in the right subtree are greater than or equal to the node's value. | |
| This class supports insertion, removal, and traversal operations. Nodes | |
| are linked via `left_node` and `right_node` references, and each node | |
| keeps an optional reference to its parent to simplify certain operations | |
| such as deletion. | |
| """ |
| if parent.right_node == node: | ||
| parent.right_node = node.right_node |
There was a problem hiding this comment.
Missing 'elif' keyword. Line 78 should be 'elif parent.right_node == node:' instead of 'if parent.right_node == node:'. Without elif, if the node is the left child of its parent, both conditions could theoretically execute (though in practice only one will be true), but using elif makes the mutual exclusivity explicit and is more correct.
|
|
||
| if parent.right_node == node: | ||
| parent.right_node = node.left_node | ||
| if parent is None: |
There was a problem hiding this comment.
Inconsistent condition structure. Line 97 should use 'elif' instead of 'if' since it's mutually exclusive with the previous conditions (lines 92-96). When parent is not None, one of the previous conditions handles the case, so this should be elif for consistency with the intended control flow.
| if parent is None: | |
| elif parent is None: |
| print("Removing a leaf node", node.data) | ||
| parent = node.parent | ||
|
|
||
| # when the leaf node is the left node of it's parent | ||
| if parent is not None and parent.left_node == node: | ||
| parent.left_node = None | ||
|
|
||
| # when the leaf node is the right node of it's parent | ||
| if parent is not None and parent.right_node == node: | ||
| parent.right_node = None | ||
|
|
||
| if parent is None: | ||
| self.root = None | ||
|
|
||
| del node | ||
|
|
||
| # when the node has a single right child | ||
| elif node.left_node is None and node.right_node is not None: | ||
| print("Removing a node with a single right child", node.data) | ||
| parent = node.parent | ||
|
|
||
| if parent is not None: | ||
| if parent.left_node == node: | ||
| parent.left_node = node.right_node | ||
| if parent.right_node == node: | ||
| parent.right_node = node.right_node | ||
| if parent is None: | ||
| self.root = node.right_node | ||
|
|
||
| node.right_node.parent = parent | ||
| del node | ||
|
|
||
| # when the node has a single left child | ||
| elif node.right_node is None and node.left_node is not None: | ||
| print("Removing a node with a single left child", node.data) | ||
| parent = node.parent | ||
|
|
||
| if parent is not None: | ||
| if parent.left_node == node: | ||
| parent.left_node = node.left_node | ||
|
|
||
| if parent.right_node == node: | ||
| parent.right_node = node.left_node | ||
| if parent is None: | ||
| self.root = node.left_node | ||
|
|
||
| node.left_node.parent = parent | ||
| del node | ||
|
|
||
| # when the node has two children | ||
| else: | ||
| print("Removing a node with two children") |
There was a problem hiding this comment.
Debug print statements should be removed or replaced with proper logging. The print statements on lines 54, 72, 88, and 105 appear to be debug output that should either be removed for production code or replaced with a proper logging mechanism for better control over output verbosity.
| if self.root: | ||
| self._in_order_traversal(self.root) | ||
| else: | ||
| print("Tree is empty") |
There was a problem hiding this comment.
Inconsistent empty tree messages. The method uses "Tree is empty" (line 123) while other traversal methods use "Tree is empty!" with an exclamation mark (lines 137, 152). Consider standardizing the error messages across all traversal methods for consistency.
| print("Tree is empty") | |
| print("Tree is empty!") |
| if data < node.data: | ||
| if node.left_node: | ||
| """ | ||
| Recursively inserts a new value into the binary search tree by comparing | ||
| data with the current node and placing it in the appropriate left or right subtree. | ||
| """ |
There was a problem hiding this comment.
The docstring is misplaced inside the conditional block. It should be placed immediately after the method definition (line 19) to properly document the entire _insert_node method. Additionally, the current docstring describes the overall insertion logic but is only present in one branch of the if statement.
| if data < node.data: | |
| if node.left_node: | |
| """ | |
| Recursively inserts a new value into the binary search tree by comparing | |
| data with the current node and placing it in the appropriate left or right subtree. | |
| """ | |
| """ | |
| Recursively inserts a new value into the binary search tree by comparing | |
| data with the current node and placing it in the appropriate left or right subtree. | |
| """ | |
| if data < node.data: | |
| if node.left_node: |
| if self.root: | ||
| self._remove_node(data, self.root) | ||
| else: | ||
| print("Tree is empty!") |
There was a problem hiding this comment.
The error message prints to stdout but the method continues execution. When the tree is empty and someone tries to remove a node, printing a message and then attempting to call _remove_node with None will result in the method returning early (line 42-43). Consider either raising an exception for better error handling or ensuring the error condition is properly communicated to the caller.
| print("Tree is empty!") | |
| raise ValueError("Cannot remove from an empty tree") |
| if parent is None: | ||
| self.root = node.right_node |
There was a problem hiding this comment.
Inconsistent spacing around 'if' statement. Line 80 has 'if parent is None:' without elif, but the previous two conditions (lines 76-79) are mutually exclusive checks that should use elif. For consistency and clarity, line 80 should also use 'elif' since if parent is not None, one of the previous conditions would have executed.
| if parent.left_node == node: | ||
| parent.left_node = node.left_node | ||
|
|
||
| if parent.right_node == node: |
There was a problem hiding this comment.
Missing 'elif' keyword. Line 95 should be 'elif parent.right_node == node:' instead of 'if parent.right_node == node:'. This is the same issue as on line 78 - using elif makes the mutual exclusivity of the conditions explicit and is more correct.
| if parent.right_node == node: | |
| elif parent.right_node == node: |
| else: | ||
| if node.right_node: | ||
| self._insert_node(data, node.right_node) | ||
| else: | ||
| node.right_node = Node(data=data, parent=node) |
There was a problem hiding this comment.
Potential issue with handling duplicate values. When data equals node.data (line 29 else branch), the value is inserted to the right. This means duplicate values are silently accepted and placed in the right subtree. Consider either explicitly rejecting duplicates or documenting this behavior, as it may lead to unexpected results during removal operations.
No description provided.