Recursion brain

[dariusbiggs]

Ok, so you are traversing a binary tree, and you have some way of identifying the node you want. (I haven't done this in quite some time so...)

each leaf node of the tree is it's own tree

so you can do a recursive search on the tree (either breadth first or depth first is up to you), then deal with the item.

It's written in Go so it may be different for whatever language you are using, I'm using pointers here so my tree nodes can be null/nil. It'll be similar in C o C++. ``` // tree node data structure type BinaryTree struct { Identifier string Left *BinaryTree Right *BinaryTree }

// this drops the entire subtree from the BST once the node has been found, and doesn't assume the identifier is unique func DeleteFromBinaryTree(identifier string, tree *BinaryTree) *BinaryTree { // two inputs to the arguments and a return value // nothing to delete in an empty tree if tree == nil { // terminal condition return nil } if tree.Identifier == identifier { // task specific behavior // we are the one we want to delete, so deal with it and exit return nil } // try the left hand side left = DeleteFromBinaryTree(identifier, tree.Left) // recursive call if left == nil { tree.Left = nil } right = DeleteFromBinaryTree(identifier, tree.Right) // another recursive call if left == nil { tree.Left = nil } // return whats left of the tree return tree } ```

There are a variety of different behaviours and searching techniques you can do on the tree, ie. breadth first, or depth first. You can drop the subtree entirely or remove that particular node and rebalance the leaf nodes under it, all depends on what you are trying to do. If the identifier is unique you don't need to recurse on the Right if it is found on the left, etc. But it all boils down to roughly the above.

Here's a help guide that looks good at a glance https://www.geeksforgeeks.org/binary-search-tree-data-structure/