Skip to main content

Deleting the leaf node in a binary tree

I am implementing a BST and everything works, even the deletion with two children.The only bug is in the deletion of a leaf which seems such a trivial task. There seem to be still a reference to the leaf node but I can’t get on top of this issue.Putting node = None doesn’t remove the entire Node.I have also tried del node without any luck.If you could spot the problem it would be nice.

import random


class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.parent = None
        self.left_child = None
        self.right_child = None
        self.level = None

class Tree:

    def __init__(self):
        self.root = None
        self.size = 0
        self.height = 0

    def _insertion(self, root, data):
        new_node = Node(data)
        if root.data < data:
            if root.right:
                return self._insertion(root.right, data)
            root.right = new_node
            root.right.parent = root
            root.right_child = root.right
            return
        if root.data > data:
            if root.left:
                return self._insertion(root.left, data)
            root.left = new_node
            root.left.parent = root
            root.left_child = root.left
            return

    def insertion(self, data):
        new_node = Node(data)
        if not self.root:
            self.root = new_node
            return
        return self._insertion(self.root, data)

    def _get_height(self, root):
        if not root:
            return -1
        left_height = self._get_height(root.left)
        right_height = self._get_height(root.right)
        return 1 + max(left_height, right_height)

    def get_height(self):
        if not self.root:
            return 0
        return self._get_height(self.root)

    def fill_random(self, num_nodes):
        for i in range(num_nodes):
            random_num = int(random.random()*100)
            self.insertion(random_num)

    def _inorder(self, root):
        if root:
            self._inorder(root.left)
            print(root.data)
            self._inorder(root.right)

    def inorder(self):
        root = self.root
        return self._inorder(root)

    def get_max(self, node):
        while node.right:
            node = node.right
        return node.data

    def search(self, data):
        root = self.root
        while root.right or root.left:
            if root.data < data:
                root = root.right
            if root.data > data:
                root = root.right
            if root.data == data:
                return root
        return None

    def _delete_node(self, root, data):
        if root:
            if root.data < data:
                return self._delete_node(root.right, data)
            if root.data > data:
                return self._delete_node(root.left, data)
            if root.data == data:
                if not root.left and not root.right:
                    root = None
                    return
                if not root.left and root.right:
                    root = root.right
                    root.right = None
                    return
                if not root.right and root.left:
                    root = root.left
                    root.left = None
                    return
                if root.right and root.left:
                    value = self.get_max(root)
                    print(f"This is the value: {value}")
                    root.data = value
                    self._delete_node(root.right, value)

    def delete_node(self, data):
        if not self.root:
            return None
        return self._delete_node(self.root, data)

if __name__ == '__main__':
    my_tree = Tree()
    my_tree.insertion(33)
    my_tree.insertion(36)
    my_tree.insertion(25)
    my_tree.insertion(20)
    my_tree.insertion(27)
    my_tree.insertion(35)
    my_tree.insertion(39)
    my_tree.delete_node(33)
    my_tree.inorder()
    my_tree.search(35)




source https://stackoverflow.com/questions/69781406/deleting-the-leaf-node-in-a-binary-tree

Comments

Popular posts from this blog

Why is my reports service not connecting?

I am trying to pull some data from a Postgres database using Node.js and node-postures but I can't figure out why my service isn't connecting. my routes/index.js file: const express = require('express'); const router = express.Router(); const ordersCountController = require('../controllers/ordersCountController'); const ordersController = require('../controllers/ordersController'); const weeklyReportsController = require('../controllers/weeklyReportsController'); router.get('/orders_count', ordersCountController); router.get('/orders', ordersController); router.get('/weekly_reports', weeklyReportsController); module.exports = router; My controllers/weeklyReportsController.js file: const weeklyReportsService = require('../services/weeklyReportsService'); const weeklyReportsController = async (req, res) => { try { const data = await weeklyReportsService; res.json({data}) console...

How to show number of registered users in Laravel based on usertype?

i'm trying to display data from the database in the admin dashboard i used this: <?php use Illuminate\Support\Facades\DB; $users = DB::table('users')->count(); echo $users; ?> and i have successfully get the correct data from the database but what if i want to display a specific data for example in this user table there is "usertype" that specify if the user is normal user or admin i want to user the same code above but to display a specific usertype i tried this: <?php use Illuminate\Support\Facades\DB; $users = DB::table('users')->count()->WHERE usertype =admin; echo $users; ?> but it didn't work, what am i doing wrong? source https://stackoverflow.com/questions/68199726/how-to-show-number-of-registered-users-in-laravel-based-on-usertype

The number of nodes and edges I calculated manually and by a method provided by networkx library dont match

I am trying to analyse a graph using networkx library in Python. I have implemented a function that returns the nodes and edges of that graph. After that I counted the number of nodes and edges by implementing the len() function for nodes and edges, which gave me 17 for both nodes and edges. However, when I used the method graph.number_of_nodes() of networkx library it gave me 53. My code: import pandas as pd import networkx as nx import matplotlib.pyplot as plt header_list = ["a","b","w"] E =pd.read_csv("aves-barn-swallow-contact-network.edges",sep=" ",header= None,names=header_list) # print(E.head()) # prints first few rows of the csv file G = nx.from_pandas_edgelist(E,"a","b",["w"]) nx.draw(G) plt.show() class GraphAnalyse: #finding nodes and edges def nodeEdge(self,Graph): nodes = Graph.nodes() edges = Graph.edges() ...