StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>If you want to delete both subtrees, there's no need to recurse. Just set <code>root.left</code> and <code>root.right</code> to <code>None</code> and let the garbage collector take care of them. Indeed, rather than making a <code>delete</code> function in the first place, you could just set <code>root = None</code> and be done with it!</p> <p><strong>Edit:</strong> If you need to run cleanup code on the data values, you might want to recurse through the tree to get to all of them if the GC doesn't do enough. Tearing down the links in the tree shouldn't really be necessary, but I'll do that too for good measure:</p> <pre><code>def delete(node): if node: node.data.cleanup() # run data value cleanup code delete(node.left) # recurse delete(node.right) node.data = None # clear pointers (not really necessary) node.left = None none.right = None </code></pre> <p>You had also asked about an iterative approach to traversing the tree, which is a little more complicated. Here's a way to an traversal using a <code>deque</code> (as a stack) to keep track of the ancestors:</p> <pre><code>from collections import deque def delete_iterative(node): stack = deque() last = None # start up by pushing nodes to the stack until reaching leftmost node while node: stack.append(node) node = node.left # the main loop while stack: node = stack.pop() # should we expand the right subtree? if node.right && node.right != last: # yes stack.append(node) node = node.right while node: # expand to find leftmost node in right subtree stack.append(node) node = node.left else: # no, we just came from there (or it doesn't exist) # delete node's contents node.data.cleanup() node.data = None # clear pointers (not really necessary) node.left = None node.right = None # let our parent know that it was us it just visited last = node </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload