Just build one level at a time, e.g.: class Node(object): def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right def traverse(rootnode): thislevel = [rootnode] while thislevel: nextlevel = list() for n in thislevel: print n.value, if n.left: nextlevel.append(n.left) if n.right: nextlevel.append(n.right) print thislevel = nextlevel t = Node(1, Node(2, Node(4, … Read more
Perfect Tree: x / \ / \ x x / \ / \ x x x x / \ / \ / \ / \ x x x x x x x x Complete Tree: x / \ / \ x x / \ / \ x x x x / \ / x x … Read more
Stumbled across this old question while searching for something else. I notice that you never did get a complete answer. The way to solve this problem is to start by writing a specification for the function you are trying to write. Specification: A well-formed binary tree is said to be “height-balanced” if (1) it is … Read more
How to fix remove in RedBlackTree implementation?
The left-child, right-sibling representation (LCRS) is a way of encoding a multi-way tree (a tree structure in which each node can have any number of children) using a binary tree (a tree structure in which each node can have at most two children). Motivation To motivate how this representation works, let’s begin by considering a … Read more
Geez, I’ll have to actually type it up from Knuth. This solution is by Joseph M. Morris [Inf. Proc. Letters 9 (1979), 197-200]. As far as I can tell, it runs in O(NlogN) time. static void VisitInO1Memory (Node root, Action<Node> preorderVisitor) { Node parent = root ; Node right = null ; Node curr ; while (parent != null) { curr … Read more
Binary tree: Tree where each node has up to two leaves 1 / \ 2 3 Binary search tree: Used for searching. A binary tree where the left child contains only nodes with values less than the parent node, and where the right child only contains nodes with values greater than or equal to the … Read more
In C++17, the new map::extract function lets you change the key. Example: std::map<int, std::string> m{ {10, “potato”}, {1, “banana”} }; auto nodeHandler = m.extract(10); nodeHandler.key() = 2; m.insert(std::move(nodeHandler)); // { { 1, “banana” }, { 2, “potato” } }
If I am reading the algorithm right, this should be an example of how it works: X / \ Y Z / \ / \ A B C D First, X is the root, so it is initialized as current. X has a left child, so X is made the rightmost right child of X‘s … Read more
Skip lists are more amenable to concurrent access/modification. Herb Sutter wrote an article about data structure in concurrent environments. It has more indepth information. The most frequently used implementation of a binary search tree is a red-black tree. The concurrent problems come in when the tree is modified it often needs to rebalance. The rebalance … Read more