This is a valid binary search tree. However, if we try to find 5, we have to traverse every node. It is no better than a linked list. Ideally, we would want every node of our binary search tree to have 2 children. This way, insertion, deletion and search would take, at worst, O(log n) time. Say the values 1 to 7 are arranged with 4 and the root node, 2 as its left child with 1 and 3 as children, and 6 as the right node with 5 and 7 as children, then every node has 2 children. This tree is meaning that balanced, is has a minimal depth relative to the number of nodes. Looking for a value in a balanced binary search tree is similar to binary search on a sorted array. In fact, if we don't need to insert or delete items, they behave exactly the same way. However, a tree structure is better for handling insertions and deletions. Maintaining a balanced tree may need the tree to be re-structured when you insert and delete. The code for this is tricky and it won't be covered here. But you can read about it in the text book. [ Presentation by Rachel Cardell-Oliver on a video by Bannus Van der Kloot for Harvard University cs50. ]
This is a valid binary search tree. However, if we try to find 5, we have to traverse every node. It is no better than a linked list. Ideally, we would want every node of our binary search tree to have 2 children. This way, insertion, deletion and search would take, at worst, O(log n) time. Say the values 1 to 7 are arranged with 4 and the root node, 2 as its left child with 1 and 3 as children, and 6 as the right node with 5 and 7 as children, then every node has 2 children. This tree is balanced, meaning that is has a minimal depth relative to the number of nodes. Looking for a value in a balanced binary search tree is similar to binary search on a sorted array. In fact, if we don't need to insert or delete items, they behave exactly the same way. However, a tree structure is better for handling insertions and deletions. Maintaining a balanced tree may need the tree to be re-structured when you insert and delete. The code for this is tricky and it won't be covered here. But you can read about it in the text book. [ Presentation by Rachel Cardell-Oliver on a video by Bannus Van der Kloot for Harvard University cs50. ]
binary-search-tree-script.docx