Popular posts

A tree in CS is a collection of nodes which are connected to other nodes in a hierarchy. The top-most node is called the "root node", and it and any node below it can have children. All nodes, except for the root node, have a parent. For example:

A binary tree is a tree in which each node has at most three connections: a parent (except for the root node!) and 0..2 children.

// TypeScript
interface Node {
    parent?: Node
    leftChild?: Node
    rightChild?: Node
    value: any
}

Trees are useful in order to represent hierarchic structures in code. For example a JSON object can be represented as a tree. In game-dev, you will find lots of quad-trees (trees with nodes which have at most four children) in 2D games, representing four adjacent field (top, right, down, left) and octrees (trees with nodes which have at most eight children) in 3D games.

Binary trees are especially useful when used as binary search trees, because it is very performant to fill the tree with items (O(n)) and just as performant to read a sorted list of items from the trees (O(n)). Searching in such a tree can be very performant, if the items from which the tree was created, weren't pre-sorted. All other operations are very trivial. Sorting works like this: You start with the first item and make it the root node. Then you compare the second item to the first. Is it smaller or bigger? If it is smaller, it goes to the left child-branch, if it is bigger it goes to the right child-branch. For any further item, you start the comparison at the root node and go down all branches until there is no more item at a branch. That's the spot where the new item is inserted as a new node. Searching is just as easy. Compare all nodes until you find a node which is the same. In case of a search tree, it makes sense to store an object with a key (for comparison) and a value (as payload) inside the node.

As for inverting the tree, I guess it depends on what kind of inversion was asked for. They might want to get a reversed version of the tree (mirrored at the Y axis), which could be achieved by switching the branches of all nodes.