Binary Search Tree - Finding the Minimum Value

Aug 2, 2018 binary search tree swift xcode
WhatsApp
During my revision of the Binary Search Tree, it seemed certain youtube videos did not cover this well enough. After a certain time, juggling different conditions, it didn't seem their implementation worked for all cases, only covering specific ones. This lead me to move to wiki to search for their approach which was to find the minimum node.

Now why should we find the minimum node. It's actually an amazing approach which exploits the Binary Tree's structure and node formation. Having only two nodes makes the deletion simpler to reorganise. By a minimum value approach, it ultimately leads to deterministic path where we can be sure that only the following conditions can be met

1. The minimum value/successor node will always be a left node (child). Left nodes are always lower than the right
2. The successor's children will only have a right node. A right node of the successor child would be greater than the parent
3. The successor's children will not have a left node. NULL. We know this because the successor is already the minimum value

The code needs tidying up but I believe it works with the test data I used. Please find it at my Github. It's written in Swift using Playground.

If you found the following info helpful, I'm happy to accept any donations of the following cryptocurrencies.

  • Bitcoin - 17DTiPExzP9StqveW428acEyB4mVMfKbiK
  • Ethereum - 0x87B8307FD20dc90cc05c94905Ec593134D32B6FF
  • Litecoin - LZMiz5U5sVq9doMLYE3gfLJrxCQDKuyCmU
  • Neo - AXv71WB38ajc1KUUEnxQKhynLLPc4BapVb