{"comment":{"url":"https://api.github.com/repos/dwhite96/data-structures/comments/10246979","html_url":"https://github.com/dwhite96/data-structures/commit/d70fe68ffa777c17e1fd83ddfb524f909ed2c6db#commitcomment-10246979","id":10246979,"user":{"login":"jfarmer","id":37304,"avatar_url":"https://avatars.githubusercontent.com/u/37304?v=3","gravatar_id":"","url":"https://api.github.com/users/jfarmer","html_url":"https://github.com/jfarmer","followers_url":"https://api.github.com/users/jfarmer/followers","following_url":"https://api.github.com/users/jfarmer/following{/other_user}","gists_url":"https://api.github.com/users/jfarmer/gists{/gist_id}","starred_url":"https://api.github.com/users/jfarmer/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/jfarmer/subscriptions","organizations_url":"https://api.github.com/users/jfarmer/orgs","repos_url":"https://api.github.com/users/jfarmer/repos","events_url":"https://api.github.com/users/jfarmer/events{/privacy}","received_events_url":"https://api.github.com/users/jfarmer/received_events","type":"User","site_admin":false},"position":55,"line":48,"path":"binary_search_tree.rb","commit_id":"d70fe68ffa777c17e1fd83ddfb524f909ed2c6db","created_at":"2015-03-17T21:20:07Z","updated_at":"2015-03-17T21:20:07Z","body":"Remember, there are four cases to deal with.  I'm going to call the value we're looking for `needle`, as in \"needle in a haystack\"\r\n\r\n1.  `needle` doesn't exist\r\n2.  `needle` exists and has no children\r\n3.  `needle` exists and has exactly one child (either left or right, but not both)\r\n4.  `needle` exists and has exactly two children (both left and right)\r\n\r\nTo handle each case:\r\n\r\n1.  If `needle` doesn't exist, there's nothing to do.\r\n2.  If `needle` has no children, remove `needle` from the tree\r\n3.  If `needle` has exactly one child...\r\n   - If `needle` has a left child but no right child, replace `needle` with the root of `needle`'s left sub-tree\r\n   - If `needle` has a right child but no left child, replace `needle` with the root of `needle`'s right sub-tree\r\n4.  If `needle` has exactly two children...\r\n    - Find the largest value in `needle`'s left sub-tree (i.e., `left_max = needle.left.max`)\r\n    - Replace the value of `needle`'s node with `left_max`\r\n    - Remove `left_max` from `needle`'s left sub-tree\r\n\r\nThis works because, by definition, the maximum value in any subtree has at most one child, i.e., it might have left (smaller) children but because it's the maximum value it can't have any right (large) children by definition.  This reduces the two-children case to either the 1-child or 0-child case, either of which we know how to solve directly.\r\n"}}