Vertical view and horizontal distance in a binary tree
The horizontal distance is a metric for the binary trees that is computed in relation to the parent and the position of the node (left, right).Â
Here is the formula:
0 for the root the left child has the distance of its parent -1 the right child has the distance of its parent +1
Between the two children of the same node, there is a horizontal distance of two. As the tree is expanded, the nodes may form vertical lines and in this case they will have the same horizontal distance.Â
Using horizontal distance, it's possible to have a nice visual representation of the tree. We are able to measure the necessary width of the window that contains the tree as the absolute difference of max distance and min distance of all nodes.
Apparently, the implementation of the binary tree pictured below ignores this ingenuous trick.
I associated integer values to the nodes that transform it into a BST, but this is not important for the example. What's relevant is the value between the parenthesis which represents the horizontal distance. The root has 0, as we go down in the left subtree, the node with value 3 has the distance -1 (0-1), node with value 2 the distance -2 (-1-1) and so on.
If you put your imagination to work, you will be able to see vertical lines connecting nodes with the same horizontal distance. There's a special case I wanted to include in here, the nodes 5 and 7 have both horizontal distance 0 so they would overlap in a graphic representation.
The code for computing horizontal distances and the complete vertical view is below. The result is a sorted dictionary that stores the horizontal distance as key that points to a list of nodes with this distance .
/// Vertical view works with the concept of horizontal distance /// The horizontal distance is computed like this: /// 0 for the root /// the left child has the distance of its parent -1 /// the right child has the distance of its parent +1 /// nodes having the same horizontal distance form a line /// the vertical view means displaying the collection of those vertical lines /// public static SortedDictionary<int, List<T>> VerticalView(NodeTree root) { var distances = new SortedDictionary<int, List<T>>(); horizontalDistance(root, 0, distances); return distances; } private static void horizontalDistance(NodeTree<T> node, int distance, SortedDictionary<int, List<T>> distances) { if (node == null) { return; } updateHorizontalDistance(x => x - 1, distance, node.Left, distances); updateHorizontalDistance(x => x + 1, distance, node.Right, distances); } private static void updateHorizontalDistance(Func<int, int> horizontalDistanceComputer, int distance, NodeTree<T> node, SortedDictionary<int, List<T>> distances) { if (node != null) { int leftDistance = horizontalDistanceComputer(distance); List<T> values; if (!distances.TryGetValue(leftDistance, out values)) { values = new List(); distances[leftDistance] = values; } values.Add(node.Data); horizontalDistance(node, leftDistance, distances); } }
