The pseudocode that you’ve posted will correctly balance a tree. That said, it is too inefficient to be practical – notice that you’re recursively exploring the entire tree trying to do rebalancing operations, which will make all insertions and deletions take O(n) time, eating away all the efficiency gains of having a balanced tree. The … Read more
All those articles talk mostly about the serialization part. The deserialization part is slightly tricky to do in one pass. I have implemented an efficient solution for deserialization too. Problem: Serialize and Deserialize a binary tree containing positive numbers. Serialization part: Use 0 to represent null. Serialize to list of integers using preorder traversal. Deserialization … Read more
For a ‘proper’ tree (see below), it’s the same thing, at least by most definitions. Like Wikipedia, for example: Breadth-first See also: Breadth-first search Trees can also be traversed in level-order, … … a breadth-first (level-order) traversal … Well, at least level-order traversal is the same as breadth-first traversal. There are many reasons to traverse … Read more
It’s a pretty well-known problem with the following answer: public boolean isValid(Node root) { return isValidBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } private boolean isValidBST(Node node, int l, int h) { if(node == null) return true; return node.value > l && node.value < h && isValidBST(node.left, l, node.value) && isValidBST(node.right, node.value, h); } The recursive call makes sure … Read more
Your question seems to be well answered here but to summarise in relation to your specific question it might be better to think of it in reverse; “what happens to the BST solution time as the number of nodes goes up”? Essentially, in a BST every time you double the number of nodes you only … Read more
The simplest possible iterator stores the last seen key, and then on the next iteration, searches the tree for the least upper bound for that key. Iteration is O(log n). This has the advantage of being very simple. If keys are small then the iterators are also small. of course it has the disadvantage of … Read more
There’s no special reason, to my knowledge – I’d guess that the reason is that for so many applications the highly-tuned dict and set implementations (which are hash tables) work well. They’re good enough in most cases. There are definitely situations where you need the performance characteristics of balanced binary search trees (like ordered traversal … Read more
Binary Search Trees A node in a binary tree is a data structure that has an element, and a reference to two other binary trees, typically called the left and right subtrees. I.e., a node presents an interface like this: Node: element (an element of some type) left (a binary tree, or NULL) right (a … Read more
Linked List: Item(1) -> Item(2) -> Item(3) -> Item(4) -> Item(5) -> Item(6) -> Item(7) Binary tree: Node(1) / Node(2) / \ / Node(3) RootNode(4) \ Node(5) \ / Node(6) \ Node(7) In a linked list, the items are linked together through a single next pointer. In a binary tree, each node can have 0, … Read more