GIF Of Inverting a binary Tree

Processing Coding Questions
1

Hi.
I am trying to create a gif, for the inversion of a binary tree(swap the left and right child of a node). For that,

  1. I have created a sketch of a binary tree first
  2. And then I am trying to redraw the tree after swapping the left and right child of a node.
    In step 2) I am stuck and don’t know how to proceed.
    If 2 is clear, then I can save a frame each time there is a redraw occurring. And using the saved frames I will be able to create the gif.
    Here is my code:
    Setup Class:
private Node node;
private PFont font;

void setup() {
  size(500, 500);
  background(220, 240, 200);
  node = new TreeNode().getFullBinaryTree(40);
  font = createFont("Arial", 50, true);
  textFont(font, 15);
  dfs(node, null);
}

void draw() {
}

void mousePressed() {
  dfs(node, null);
}

void invert(Node node) {
  if (node == null) return;
  Node temp = node.left;
  node.left = node.right;
  node.right = temp;
  invert(node.left);
  invert(node.right);
}

void dfs(Node nod, Node parent) {
   if (parent != null && nod != null) {
      parent.join(nod); 
   }
   if (nod == null) return;
   nod.drawNode();
   dfs(nod.left, nod);
   dfs(nod.right, nod);
}

Node Class:

class Node {
  private int val;
  private Cen center;
  private int dia;
  private int rad;
  private Node left;
  private Node right;
  private Color col;

  public Node(int val, Cen center, int dia, Node left, Node right, Color col) {
    this.val = val;
    this.center = center;
    this.dia = dia;
    this.left = left;
    this.right = right;
    this.rad = dia / 2;
    this.col = col;
  }
  
  public void drawNode() {
    switch(col) {
       case RED:
         fill(255, 0, 0);
         break;
        case BLUE:
          fill(0, 255, 0);
          break;
        default:
          break;
    }
    ellipse(center.x, center.y, dia, dia);
    fill(0, 0, 0);
    text(""+val+"", center.x - 8,center.y + 4); 
  }
  
  public void join(Node other) { // joins two node by a line
     line(center.x, center.y + rad, other.center.x, other.center.y - rad); 
  }
  
  @Override
    public String toString() {
    return "Node: {" + val +"," + center+"," + dia+"}";
  }
}

Center Class:

class Cen {
  int x;
  int y;

  public Cen(int x, int y) {
    this.x = x;
    this.y = y;
  }
  @Override
    public String toString() {
    return "Center: {" + x +"," + y+"}";
  }
}

Color Enum:

enum Color {
 RED("#FF0000"),
 BLUE("#0000FF"),
 UNKNOWN("unknown");
 
 private String col;
 private Color(String col) {
   this.col = col;
 }
 
 public String getColor() {
   return col;
 }
}

NodeBuilder class:

class NodeBuilder {
  private int val;
  private Cen center;
  private int dia;
  private Node left;
  private Node right;
  private Color col;

  public NodeBuilder center(Cen center) {
    this.center = center;
    return this;
  }

  public NodeBuilder val(int val) {
    this.val = val;
    return this;
  }

  public NodeBuilder dia(int dia) {
    this.dia = dia;
    return this;
  }

  public NodeBuilder left(Node left) {
    this.left = left;
    return this;
  }

  public NodeBuilder right(Node right) {
    this.right = right;
    return this;
  }

  public NodeBuilder col(Color col) {
    this.col = col;
    return this;
  }
  public Node build() {
    return new Node(val, center, dia, left, right, col);
  }
}

TreeCreation Class:

class TreeNode {
  Node root = null;
  int w = width /2;
  int h = height / 7;
  // manually build a binary tree sketch
  public Node getFullBinaryTree(int dia) {
    if (root == null) {
      root = getNode(10, dia, new Cen(w, h), Color.UNKNOWN);
    }
    root.left = getNode(20, dia, new Cen(w - 80, h + 80), Color.BLUE);
    root.right = getNode(30, dia, new Cen(w + 80, h + 80), Color.RED);
    root.left.left = getNode(20, dia, new Cen(w - 130, h + 180), Color.BLUE);
    root.left.right = getNode(20, dia, new Cen(w - 30, h + 180), Color.RED);
    root.right.left = getNode(20, dia, new Cen(w + 30, h + 180), Color.BLUE);
    root.right.right = getNode(10, dia, new Cen(w + 130, h + 180), Color.RED);
    return root;
  }

  public Node getNode(int val, int dia, Cen center, Color col) {
    return new NodeBuilder()
      .val(val)
      .dia(dia)
      .center(center)
      .col(col)
      .build();
  }
}

Can someone help me?

1 Like
2

Welcome to the forums, and thanks for the nicely formatted code!

It looks like you have all the pieces there, and unless I don’t understand your question, I think it should look something like this:

  1. Draw the tree. Save this first frame.
  2. Call invert() on the root
  3. Inside invert(), draw the new changes and save(), before the recursive calls below.

This does mean adding some more code to invert(). But if you’re a stickler for code purity, perhaps you can write an augmented version called saveInvert() or something that implements the changes above.

1 Like
3

Hi. Thanks for the reply. I actually tried your point 3) with no success. Are you saying I need to call DFS to draw the tree again inside invert method after performing swap operation?

4

This might be redundant, but for now I would have a function that draws

void invertAndDraw(Node node, Node root) {

  // draw current state of tree
  drawEntireTree(root);
  // save() current canvas
  save();

  if (node == null) return;
  Node temp = node.left;
  node.left = node.right;
  node.right = temp;
  invertAndDraw(node.left);
  invertAndDraw(node.right);
}
5

It looks to me (without extensive testing) like you have a conceptual problem. You store the child nodes in .left and .right. But you don’t dynamically lay out your graph based on .left and .right position. Instead, you hard-code the x,y position of each node into .center.

This means that you can swap .left and .right all you want, but the x,y location on screen will stay the same. You either need to update the x,y when you swap or you need to stop storing the x,y in the nodes, and just walk the binary tree to draw it dynamically.

1 Like
6

As an alternative to storing x and y in nodes, you might want to consider using recursion for just-in-time rendering.

For example, what if a Node class could recursively draw its sub-nodes (if they existed). Then passing an x and y into any node at draw time would also render all sub-nodes with correct spacing.

class Node {
  String val;
  color c;
  Node left;
  Node right;
  Node(String val) {
    this.val = val;
    c = color(random(128, 255), random(128, 255), random(128, 255));
  }

  void draw(float x, float y) {
    pushStyle();
    fill(c);
    ellipse(x, y, 20, 20);
    fill(0);
    text(val, x-4, y+5);
    popStyle();
  }

  void drawAll(float x, float y, float span, float row) {
    float span2 = span*0.5;
    if (left!=null) {
      line(x, y, x-span, y+row);
      left.drawAll(x-span, y+row, span2, row);
    }
    if (right!=null) {
      line(x, y, x+span, y+row);
      right.drawAll(x+span, y+row, span2, row);
    }
    draw(x, y);
  }
}

Note that a similar recursive approach can be taken to swapping.

  void swap() {
    Node tmp = left;
    left = right;
    right = tmp;
  }
  
  void swapAll() {
    if (left!=null) left.swapAll();
    if (right!=null) right.swapAll();
    swap();
  }