CODEWITHSUNDEEP
dartbinary-tree
Suragch
Suragch

Reputation: 511538

How to print binary tree diagram in Dart?

I have a binary tree node like this:

class BinaryTreeNode<T> {
  BinaryTreeNode(this.value, {this.leftChild, this.rightChild});
  T value;
  BinaryTreeNode? leftChild;
  BinaryTreeNode? rightChild;
}

I'd like to add a toString method so that I can have a visual representation of the contents of the binary tree.

This is a Dart version of this Java question. I was able to port one of the answers there so I am adding it below.

Upvotes: 0

Views: 542

Answers (1)

Suragch
Suragch

Reputation: 511538

Here is a modified version of this answer:

class BinaryTreeNode<T> {
  BinaryTreeNode(this.value, {this.leftChild, this.rightChild});
  T value;
  BinaryTreeNode<T>? leftChild;
  BinaryTreeNode<T>? rightChild;

  @override
  String toString() {
    final out = StringBuffer();

    rightChild?._buildTree(out, true, '');
    out.writeln(value);
    leftChild?._buildTree(out, false, '');

    return out.toString();
  }

  void _buildTree(StringBuffer out, bool isRight, String indent) {
    rightChild?._buildTree(out, true, indent + (isRight ? '     ' : '│    '));

    out
      ..write(indent)
      ..write(isRight ? '┌─── ' : '└─── ')
      ..writeln(value);

    leftChild?._buildTree(out, false, indent + (isRight ? '│    ' : '     '));
  }
}

If you build a tree like so:

void main() {
  final tree = BinaryTreeNode('D',
      leftChild: BinaryTreeNode('A'),
      rightChild: BinaryTreeNode(
        'R',
        leftChild: BinaryTreeNode('T'),
        rightChild: BinaryTreeNode('Fun'),
      ));
  print(tree);
}

The output looks like this:

     ┌─── Fun
┌─── R
│    └─── T
D
└─── A

Feel free to modify my answer to simply the code. I feel like the toString method could be simplified to not repeat so much code.

Suggested solution from lrn

The following solution is more efficient since we are avoiding creating intermediate string objects as we go though the tree structure. Thanks to lrn for suggesting this approach:

class BinaryTreeNode<T> {
  BinaryTreeNode(this.value, {this.leftChild, this.rightChild});

  T value;
  BinaryTreeNode<T>? leftChild;
  BinaryTreeNode<T>? rightChild;

  @override
  String toString() {
    final out = StringBuffer();

    final indents = <String>[];
    rightChild?._buildTree(out, true, indents);
    out.writeln(value);
    leftChild?._buildTree(out, false, indents);

    return out.toString();
  }

  void _buildTree(StringBuffer out, bool isRight, List<String> indents) {
    if (rightChild != null) {
      indents.add(isRight ? '     ' : '│    ');
      rightChild!._buildTree(out, true, indents);
      indents.removeLast();
    }

    out
      ..writeAll(indents)
      ..write(isRight ? '┌─── ' : '└─── ')
      ..writeln(value);

    if (leftChild != null) {
      indents.add(isRight ? '│    ' : '     ');
      leftChild!._buildTree(out, false, indents);
      indents.removeLast();
    }
  }
}

Upvotes: 4

Related Questions