How to write a list of tree vertices base on its degree

I want to write a list of vertices of a tree so that it starts from the vertex in the branch with one degree and then decreases from the next vertex to the degree of the previous vertex.If its degree is also one, it should be read, otherwise it should pass through that vertex, and its adjacent vertices should be written if it was one degree. This process continues until its degree decreases and reaches one, then it should be read. plz help me

Answer 1

[Ayush]

Hi @fatem portosi,

You are trying to traverse a tree and output a list of vertices such that:

1. You start from a leaf node (a node with degree 1).
2. At each step:

• Move to the next connected vertex.
• Only "read" (output) a vertex if its degree is 1, or if its degree is less than the previous vertex’s degree.
• If not, pass through it and explore its adjacent vertices.

3. This continues until you reach another vertex with degree 1.

The following algorithm can be defined for the achieving the required tasks:

1. Build the tree from input edges.
2. Find a leaf node (any node with degree 1).
3. Traverse the tree from this leaf node with the custom logic:

• Keep track of the degree of the previous node.
• If current node degree < previous node degree => read it.
• If current node degree == 1 => read it.
• Else => keep traversing until above condition is met.

4. Stop when you reach another leaf.

Here is a pesudo MATLAB code for the same:

function result = custom_tree_traversal(n, edges)
    % I am building an adjacency list here
    adj = cell(n, 1);
    degree = zeros(n, 1);

    for i = 1:size(edges, 1)
        u = edges(i, 1);
        v = edges(i, 2);
        adj{u} = [adj{u}, v];
        adj{v} = [adj{v}, u];
        degree(u) = degree(u) + 1;
        degree(v) = degree(v) + 1;
    end

    % Now, Find a starting leaf node (node with degree == 1)
    start = find(degree == 1, 1);

    visited = false(n, 1);
    result = [];

    % Start DFS from the leaf with "infinite" previous degree
    dfs(start, inf);

    function dfs(u, prev_deg)
        visited(u) = true;
        curr_deg = degree(u);

        % Read if it's a leaf or has lower degree than previous
        if curr_deg == 1 || curr_deg < prev_deg
            result(end+1) = u;
        end

        % Visit adjacent unvisited nodes
        for i = 1:length(adj{u})
            v = adj{u}(i);
            if ~visited(v)
                dfs(v, curr_deg);
            end
        end
    end
end

You can read more about "dfs" algorithm here:https://www.mathworks.com/help/matlab/ref/graph.dfsearch.html

Hope it helps!