Problem

Given an expression tree, generate graphical representation of it.

Examples

Example 1

1
2
3
4
5
6
7
8
9

 Input: Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
 Output:
 Graphical Representation:
         +
       /   \
      1     *
           /   \
          2     3
 Explanation: The root of the expression tree is `+`. Its left child is `1`, and its right child is `*`. The `*` node has two children: `2` and `3`.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

 Input: Tree('-', Tree('/', Tree(8), Tree(4)), Tree(7))
 Output:
 Graphical Representation:
         -
       /   \
      /     7
     /
    /
   /
  /
  /
  8
  /
  4
 Explanation: The root of the expression tree is `-`. Its left child is `/`, and its right child is `7`. The `/` node has two children: `8` and `4`.

Solution

Method 1 - Using preorder Traversal

First lets look at expression tree:

  • Each node either contains an operator (+, -, *, /) or an operand (1, 2, etc.).
  • Operators are located at non-leaf nodes, while operands are at leaf nodes.

The visualisation involves traversing the tree and presenting the parent-child relationships. This can be implemented using either a DFS preorder traversal for node positioning or rendering with tools like matplotlib and networkx.

Approach

  • Step 1: Define the Tree class to encapsulate the structure of a binary tree.
  • Step 2: Traverse the tree recursively and build a graphical or hierarchical representation.
  • Step 3: Create a text-based or graphical representation using libraries for plotting or indentation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.util.*;

public class Solution {

    // Tree node class
    static class Tree {
        String value;
        Tree left, right;

        Tree(String value) {
            this.value = value;
        }

        Tree(String value, Tree left, Tree right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    // Solution: Print tree representation
    public void printTree(Tree root, String prefix, boolean isLeft) {
        if (root != null) {
            System.out.println(prefix + (isLeft ? "├── " : "└── ") + root.value);
            printTree(root.left, prefix + (isLeft ? "│   " : "    "), true);
            printTree(root.right, prefix + (isLeft ? "│   " : "    "), false);
        }
    }

    public static void main(String[] args) {
        // Example trees
        Tree tree1 = new Tree("+", new Tree("1"), new Tree("*", new Tree("2"), new Tree("3")));
        Tree tree2 = new Tree("-", new Tree("/", new Tree("8"), new Tree("4")), new Tree("7"));

        Solution solution = new Solution();

        // Print textual representation
        System.out.println("Tree 1:");
        solution.printTree(tree1, "", false);

        System.out.println("\nTree 2:");
        solution.printTree(tree2, "", false);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import matplotlib.pyplot as plt
import networkx as nx

# Tree class definition
class Tree:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


# Solution class
class Solution:
    def __init__(self):
        self.graph = nx.DiGraph()

    def build_graph(self, node, parent=None):
        """
        Recursively adds nodes and edges to the graph for graphical representation.
        """
        if not node:  # If the node is None, return
            return

        self.graph.add_node(str(node.value))  # Add current node
        if parent:
            self.graph.add_edge(str(parent.value), str(node.value))  # Connect to parent

        # Recursively add left and right children
        self.build_graph(node.left, node)
        self.build_graph(node.right, node)

    def draw_tree(self, tree):
        """
        Generate and display graphical representation of the given tree.
        """
        self.build_graph(tree)  # Build graph structure from tree

        # Position nodes using GraphViz layout
        pos = nx.nx_agraph.graphviz_layout(self.graph, prog="dot")
        nx.draw(self.graph, pos, with_labels=True, arrows=False, node_size=2000, node_color="skyblue")
        plt.show()


# Example usage:
tree1 = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))
tree2 = Tree('-', Tree('/', Tree(8), Tree(4)), Tree(7))

solution = Solution()
solution.draw_tree(tree1)  # Graphical representation of tree1
solution.draw_tree(tree2)  # Graphical representation of tree2

Complexity

  • ⏰ Time complexity: O(n). We traverse all n nodes in the tree to build the graphical representation.
  • 🧺 Space complexity: O(h). The space depends on the height h of the tree due to recursion stack usage.