One method which I like is to store the preorder traversal, but also include the ‘null’ nodes in there. Storing the ‘null’ nodes removes the need for also storing the inorder of the tree. Some advantages of this method You can do better storage than pre/post + inorder method in most practical cases. Serialization just … Read more
You can use recursion. We swap the left and right child of a node, in-place, and then do the same for its children: static void reverseTree(final TreeNode root) { final TreeNode temp = root.right; root.right = root.left; root.left = temp; if (root.left != null) { reverseTree(root.left); } if (root.right != null) { reverseTree(root.right); } } … Read more
What you need is a way to look up some data given a key. With the key being an unsigned int, this gives you several possibilities. Of course, you could use a std::map: typedef std::map<unsigned int, record_t> my_records; However, there’s other possibilities as well. For example, it’s quite likely that a hash map would be … Read more
Actually, people do use k-ary trees for arbitrary k. This is, however, a tradeoff. To find an element in a k-ary tree, you need around k*ln(N)/ln(k) operations (remember the change-of-base formula). The larger your k is, the more overall operations you need. The logical extension of what you are saying is “why don’t people use … Read more
Pre-order is one type of DFS. There are three types of depth-first traversal: pre-order, in-order, and post-order. Check out here for more info.
Algorithmic complexity is the same, since O(logb n) = O(c log n) = O(log n) but the constant factors, which are hidden in big-O notation, could vary noticeably, depending on implementation and hardware. B-trees were designed for platter hard disks, which have a large access time (moving the head into position) after which an entire … Read more
I ROOT (root is also an INTERNAL NODE, unless it is leaf) / \ I I INTERNAL NODES / / \ o o o EXTERNAL NODES (or leaves) As the wonderful picture shows, internal nodes are nodes located between the root of the tree and the leaves. Note that the root is also an internal … Read more
How about Morris Inorder tree traversal? Its based on the notion of threaded trees and it modifies the tree, but reverts it back when its done. Linkie: http://geeksforgeeks.org/?p=6358 Doesn’t use any extra space.
Red Black trees are good for creating well-balanced trees. The major problem with binary search trees is that you can make them unbalanced very easily. Imagine your first number is a 15. Then all the numbers after that are increasingly smaller than 15. You’ll have a tree that is very heavy on the left side … Read more
How about calling mirrorEquals(root.left, root.right) on the following function :- boolean mirrorEquals(BTree left, BTree right) { if (left == null || right == null) return left == null && right == null; return left.value == right.value && mirrorEquals(left.left, right.right) && mirrorEquals(left.right, right.left); } Basically compare the left subtree and inverted right subtree, drawing an imaginary … Read more