Please explain a binary tree to me

[Solarion]

Hi guys. Please can you shed a little light on this output I get. I basically don't get what this series of numbers means. I can't grasp how it represents the whole node tree!

using System;
  
public class Tree
{
    Node root;

    // Tree Node
    public class Node
    {
        public int data;
        public Node left, right;
        public Node(int data)
        {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    // Function to insert nodes in level order
    public Node insertLevelOrder(int[] arr,
                            Node root, int i)
    {
        // Base case for recursion
        if (i < arr.Length)
        {
            Node temp = new Node(arr[i]);
            root = temp;

            // insert left child
            root.left = insertLevelOrder(arr,
                            root.left, 2 * i + 1);

            // insert right child
            root.right = insertLevelOrder(arr,
                            root.right, 2 * i + 2);
        }
        return root;
    }

    // Function to print tree
    // nodes in InOrder fashion
    public void inOrder(Node root)
    {
        if (root != null)
        {
            inOrder(root.left);
            Console.Write(root.data + " ");
            inOrder(root.right);
        }
    }

    // Driver code
    public static void Main(String []args)
    {
        Tree t2 = new Tree();
        int []arr = { 1, 2, 3, 4, 5, 6, 6, 6, 6 };
        t2.root = t2.insertLevelOrder(arr, t2.root, 0);
        t2.inOrder(t2.root);
    }
}

Output: 6 4 6 2 5 1 6 3 6

Source Article

 

[TheMightyQuin]

 

[Solarion]

View attachment 1138010

Tell me about it. This one I stumbled into recently.

Captain Jack Sparrow and his pirate friends have been drinking one night. After plenty of rum, they got into an argument about who is the best shot. Captain Jack takes up some paint and paints a target on a nearby wall. The pirates take out their guns and start shooting.

Your task is to help the drunk pirates find out which shots hit the target.

Captain Jack Sparrow drew the target by drawing N lines. The lines form a convex shape defined by N corners. A convex shape has all internal angles less than 180 degrees. For example, all internal angles in a square are 90 degrees.

A shot within the convex shape or on one of the lines is considered a hit.

Coding Games and Programming Challenges to Code Better

CodinGame is a challenge-based training platform for programmers where you can play with the hottest programming topics. Solve games, code AI bots, learn from your peers, have fun.

www.codingame.com

Spoiler: Solution

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;

class Solution
{
    static bool estDansFigure(Point[] polygon, double px, double py)
    {
        bool impact = false;
       
        for (int current = 0; current < polygon.Length; current++)
        {
            Point vc = polygon[current];
            Point vn = polygon[(current + 1) % polygon.Length];
           
            bool btv = (vc.Y > py) != (vn.Y > py);
            bool jct = px < (vn.X - vc.X) * (py - vc.Y) / (vn.Y - vc.Y) + vc.X;
   
            if (btv && jct)
            {
                impact = !impact;
            }
        }
        return impact;
    }
   
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
       
        Point[] coins = new Point[N];
       
        for (int i = 0; i < N; i++)
        {
            string[] coinXY = Console.ReadLine().Split(' ');
            int coinX = int.Parse(coinXY[0]);
            int coinY = int.Parse(coinXY[1]);
           
            coins[i] = new Point(coinX, coinY);
        }
       
        int M = int.Parse(Console.ReadLine());
       
        for (int i = 0; i < M; i++)
        {
            string[] shotXY = Console.ReadLine().Split(' ');
            int shotX = int.Parse(shotXY[0]);
            int shotY = int.Parse(shotXY[1]);
           
            if (estDansFigure(coins, shotX, shotY))
            {
                Console.WriteLine("hit");
            }
            else
            {
                Console.WriteLine("miss");
            }
        }
    }
}

I didn't solve this though. Solution sourced from Github.

 

[cguy]

Hi guys. Please can you shed a little light on this output I get. I basically don't get what this series of numbers means. I can't grasp how it represents the whole node tree!

using System;
 
public class Tree
{
    Node root;

    // Tree Node
    public class Node
    {
        public int data;
        public Node left, right;
        public Node(int data)
        {
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    // Function to insert nodes in level order
    public Node insertLevelOrder(int[] arr,
                            Node root, int i)
    {
        // Base case for recursion
        if (i < arr.Length)
        {
            Node temp = new Node(arr[i]);
            root = temp;

            // insert left child
            root.left = insertLevelOrder(arr,
                            root.left, 2 * i + 1);

            // insert right child
            root.right = insertLevelOrder(arr,
                            root.right, 2 * i + 2);
        }
        return root;
    }

    // Function to print tree
    // nodes in InOrder fashion
    public void inOrder(Node root)
    {
        if (root != null)
        {
            inOrder(root.left);
            Console.Write(root.data + " ");
            inOrder(root.right);
        }
    }

    // Driver code
    public static void Main(String []args)
    {
        Tree t2 = new Tree();
        int []arr = { 1, 2, 3, 4, 5, 6, 6, 6, 6 };
        t2.root = t2.insertLevelOrder(arr, t2.root, 0);
        t2.inOrder(t2.root);
    }
}

Output: 6 4 6 2 5 1 6 3 6

Source Article

Imagine tracing a line around the binary tree, and for each node you write out its value only when your trace goes from the left side of a node’s children to the right. That is what an in order walk is, and those are the numbers it would print out from the tree.

Eg. The green bits in this diagram:

 

[Solarion]

@cguy Thanks that helps a lot!

 

[cguy]

Tell me about it. This one I stumbled into recently.

Coding Games and Programming Challenges to Code Better

CodinGame is a challenge-based training platform for programmers where you can play with the hottest programming topics. Solve games, code AI bots, learn from your peers, have fun.

www.codingame.com

Spoiler: Solution

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;

class Solution
{
    static bool estDansFigure(Point[] polygon, double px, double py)
    {
        bool impact = false;
   
        for (int current = 0; current < polygon.Length; current++)
        {
            Point vc = polygon[current];
            Point vn = polygon[(current + 1) % polygon.Length];
       
            bool btv = (vc.Y > py) != (vn.Y > py);
            bool jct = px < (vn.X - vc.X) * (py - vc.Y) / (vn.Y - vc.Y) + vc.X;

            if (btv && jct)
            {
                impact = !impact;
            }
        }
        return impact;
    }

    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
   
        Point[] coins = new Point[N];
   
        for (int i = 0; i < N; i++)
        {
            string[] coinXY = Console.ReadLine().Split(' ');
            int coinX = int.Parse(coinXY[0]);
            int coinY = int.Parse(coinXY[1]);
       
            coins[i] = new Point(coinX, coinY);
        }
   
        int M = int.Parse(Console.ReadLine());
   
        for (int i = 0; i < M; i++)
        {
            string[] shotXY = Console.ReadLine().Split(' ');
            int shotX = int.Parse(shotXY[0]);
            int shotY = int.Parse(shotXY[1]);
       
            if (estDansFigure(coins, shotX, shotY))
            {
                Console.WriteLine("hit");
            }
            else
            {
                Console.WriteLine("miss");
            }
        }
    }
}

I didn't solve this though. Solution sourced from Github.

So this is just a standard “point in convex polygon test”, which involves visiting each edge of the polygon, and testing a point against it (ie, which side of the edge it lies).

A trivial solution would be to test if all points are inside by verifying that the point is inside of all edge implied half-planes.

If you think it likely that the point could lie outside (likely, given that they’re drunk), you can stop at the first plane the point is outside of (an optimization the above solution doesn’t have).

Also, the solution given is using an insidedness test for non-convex polygons, which is why they can’t exit early, which is quite inefficient.

Also, there’s no reason to divide when doing the test, which would make the code run a lot faster.

Beyond that, using a bounding box or circle could accelerate rejection speed, making it run a lot faster.

 

[animal531]

So this is just a standard “point in convex polygon test”, which involves visiting each edge of the polygon, and testing a point against it (ie, which side of the edge it lies).

A trivial solution would be to test if all points are inside by verifying that the point is inside of all edge implied half-planes.

If you think it likely that the point could lie outside (likely, given that they’re drunk), you can stop at the first plane the point is outside of (an optimization the above solution doesn’t have).

Also, the solution given is using an insidedness test for non-convex polygons, which is why they can’t exit early, which is quite inefficient.

Also, there’s no reason to divide when doing the test, which would make the code run a lot faster.

Beyond that, using a bounding box or circle could accelerate rejection speed, making it run a lot faster.

Yeah prune shots that are outside the bounding box, then test line intersections (for example left to right from the hit). If you hit an odd number of lines you're in a target, if you hit an even number you're outside)

 

[cguy]

Yeah prune shots that are outside the bounding box, then test line intersections (for example left to right from the hit). If you hit an odd number of lines you're in a target, if you hit an even number you're outside)

According to the problem setup, there is just one convex polygon, so you don’t need the odd even test.

It also occurred to me that you can use an inscribed circle for trivial acceptance.

 

[ScottulusMaximus]

How dare you assume trees are binary! What if one identifies as a small shrub?